{
 "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",
   "execution_count": 117,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 0
    },
    "id": "lzaavW96tcxM",
    "outputId": "e2dfb38f-a41c-4fc8-8dc7-163c8d28ffc5"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The example summary is 116 words long, so you could write an additional 384 words.\n"
     ]
    }
   ],
   "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)))"
   ]
  },
  {
   "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",
   "execution_count": 118,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 0
    },
    "id": "8DvZ57A-djo1",
    "outputId": "fa5fc06f-8e5f-4647-c525-bfcfc060250f"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The length in words is 500\n",
      "The length in characters is 3030\n",
      "ultrices vitae auctor eu augue ut lectus arcu bibendum at varius  vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet  bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae  tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh  venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut  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  scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
      " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget  nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis  elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis  enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor  massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus  imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque  penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae  ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan  lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla  pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer  quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa  tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc  consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor  lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero  justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam  vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris  pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam  adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo  nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in  eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod  quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras  ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum  suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque  dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris  in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in  pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet  risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum  sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit  volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in  dictum non consectetur a erat nam at lectus urna\n"
     ]
    }
   ],
   "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))\n",
    "print(placeholder)"
   ]
  },
  {
   "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",
   "execution_count": 119,
   "metadata": {
    "id": "2RECnJArJew4"
   },
   "outputs": [],
   "source": [
    "name = \"\"\n",
    "permission = True\n",
    "anonymous = True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "GZZXyrV-xuAp"
   },
   "source": [
    "# Module 8 - Markov Decision Process"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 120,
   "metadata": {
    "id": "Y2NfE1CKxzS-"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA Chapter 16, “Making Simple Decisions” (16.1-16.3)\n",
    "\n",
    "equation1 = r\"\"\" $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(RESULT(a)=s')U(s')$ \"\"\"\n",
    "\n",
    "chapter16_1 = \"\"\" \n",
    "The agents has some available actions “a” and P(s) to possible states “s”.\"\"\"+\"\\n\"+\"\"\"\n",
    "Transition model P(s’|s,a) the probability that action a in state s reaches state s’ \"\"\"+\"\\n\"+\"\"\"\n",
    "Decision theory deals with choosing among actions based on the desirability of their immediate outcomes, which means the environment is assumed to be episodic \"\"\"+\"\\n\"+\"\"\"\n",
    "Utility function U(s) assign a single number to express the desirability of a state \"\"\"+\"\\n\"+\"\"\"\n",
    "The expected utility of an action EU(a) is just the average utility value of the outcomes \"\"\"+\"\\n\"+equation1+\"\\n\"+\"\"\"\n",
    " The principle of maximum expected utility (MEU): a rational agent should choose that action that maximizes the agent’s expected utility: action = argmax EU(a) \"\"\"+\"\\n\"+\"\"\"\n",
    "However, an agent may not know human’s true utility function, so decision theory is just a basic math framework to define AI problem not a panacea. \n",
    " \"\"\"\n",
    "chapter16_2 =  \"\"\" \n",
    "The agent’s preference \"\"\"+\"\\n\"+\"\"\"\n",
    "1.  A ≻ B the agent prefers A over B \n",
    "2.  A ∼ B the agent is indifferent between them \n",
    "\n",
    "We think of outcomes for every action as a lottery and there are 6 axioms of utility theory about preferences \"\"\"+\"\\n\"+\"\"\"\n",
    "Orderability: a rational agent cannot refuse to decide, it can only prefer one or indifferent \"\"\"+\"\\n\"+\"\"\"\n",
    "Exactly one of (A ≻ B), (B ≻ A), or (A ∼ B) holds. \"\"\"+\"\\n\"+\"\"\"\n",
    "Transitivity: \"\"\"+\"\\n\"+\"\"\"\n",
    "(A ≻ B) ∧ (B ≻ C) ⇒ (A ≻ C) \"\"\"+\"\\n\"+\"\"\"\n",
    "Continuity: if B is between A and C in preference, then there is some probability P that the rational agent will be indifferent between getting B for sure and the lottery that yields A with probability p and C with probability 1-p \"\"\"+\"\\n\"+\"\"\"\n",
    "A ≻ B ≻ C ⇒ ∃ p  [p,A; 1 − p,C] ∼ B \"\"\"+\"\\n\"+\"\"\"\n",
    "Substitutability: if an agent is indifferent between two lotteries A,B then it is indifferent between two more lotteries that are the same except B is substituted for A \"\"\"+\"\\n\"+\"\"\"\n",
    "A ∼ B ⇒ [p,A; 1 − p,C] ∼ [p,B; 1 − p,C]  can also change ~ to ≻ \"\"\"+\"\\n\"+\"\"\"\n",
    "Monotonicity: if two lottery has outcomes A and B, if an agent prefers A to B, then it mush prefer the lottery that has a higher probability for A \"\"\"+\"\\n\"+\"\"\"\n",
    "A ≻ B ⇒ (p > q   ⇔   [p,A; 1 − p,B] ≻ [q,A; 1 − q,B]) \"\"\"+\"\\n\"+\"\"\"\n",
    "Decomposability: compound lotteries can be reduced to simpler ones using the law of probability, no gambling \"\"\"+\"\\n\"+\"\"\"\n",
    "The 6 axions derive following additional  consequences: \"\"\"+\"\\n\"+\"\"\"\n",
    "Existence of utility function: there exists U such that  \"\"\"+\"\\n\"+\"\"\"\n",
    "U(A) > U(B)   ⇔   A ≻ B and U(A) = U(B)   ⇔   A ∼ B \"\"\"+\"\\n\"+\"\"\"\n",
    "The agent’s behavior will not change if U′(S) = aU(S) + b \"\"\"+\"\\n\"+\"\"\"\n",
    "Expected utility of a lottery: is the sum of the probability of each outcome times the utility of that outcome \"\"\"+\"\\n\"+\"\"\"\n",
    "U([p1, S1;…; pn, Sn]) =ΣpiU(Si) \"\"\"+\"\\n\"+\"\"\"\n",
    " \"\"\"\n",
    "chapter16_3 =  \"\"\" \n",
    "If we want to build AI that helps a human to make decision, we must figure out human’s utility function. The process is called preference elicitation which involves listing choices and use the preference to derive utility function.  \"\"\"+\"\\n\"+\"\"\"\n",
    "Normalized utilities: use a scale u⊥ = 0 u⊤ = 1, the agent will choose between S, a particular prize, and lottery [p, u⊤; (1 − p), u⊥], p is adjusted until the agent is indifferent S and lottery. Once this is done for each prize, the utilities for all lotteries involving those prizes are determined \"\"\"+\"\\n\"+\"\"\"\n",
    "One value to represent people’s life is micromort, which is a million chance of death. \"\"\"+\"\\n\"+\"\"\"\n",
    "Another measure is QALU, or quality adjusted life year. People are willing to accept a shorter life expectancy to avoid a disability. \"\"\"+\"\\n\"+\"\"\"\n",
    "\"\"\"+\"\\n\"+\"\"\"\n",
    "Utility of money: \"\"\"+\"\\n\"+\"\"\"\n",
    "1. EMV is the expected monetary value \n",
    "2. The utility of money was proportional to the log of the amount based on Grayson study. most people have a utility function that is concave for positive wealth, or risk averse, people prefer a sure thing with a payoff that is less than the EMV of a gamble. Looking at the positive part of the curve, U(L) < U(SEMV (L)).\n",
    "3. However, in the negative wealth, people tend to be risk seeking.\n",
    "4. The difference between the EMV and its certainty equivalent is called insurance premium, which insurance industry believes the premium is positive.\n",
    "5. Linear curve is risk neutral \n",
    "\n",
    "In reality, we usually under estimate. \"\"\"+\"\\n\"+\"\"\"\n",
    "A rational agent should act based on a normative theory, but actual agent acts with descriptive theory, explained by certainty effect that people are attracted to gains that are certain. People dislike ambiguity aversion (1/3 vs 2/3), and like framing effect (90% survival rate vs 10% death rate), prefer anchoring effect ($200 vs $50 with relative utility judgement) \n",
    " \"\"\"\n",
    "\n",
    "equation2 = r\"\"\" $U(s) = max\\sum_s P(s'|s,a)[R(s,a,s')+γU(s')]$ \"\"\"\n",
    "equation3 = r\"\"\" $Q(s,a) = max\\sum_s P(s'|s,a)[R(s,a,s')+γmaxQ(s',a')]$ \"\"\"\n",
    "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
    "chapter17_1 = \"\"\" \n",
    "Several rules: \"\"\"+\"\\n\"+\"\"\"\n",
    "The environment is fully observable \"\"\"+\"\\n\"+\"\"\"\n",
    "But not deterministic \"\"\"+\"\\n\"+\"\"\"\n",
    "If the agent bumps into a wall, it stays in the same square \"\"\"+\"\\n\"+\"\"\"\n",
    "The transition model describes the outcome of each action in each state. Because the outcome is stochastic, T(s,a,s’) represents the probability of reaching state s’ if action a is done in state s. \"\"\"+\"\\n\"+\"\"\"\n",
    "Assume the transitions are Markovian, the probability of reaching s’ from s depends only on s and not on the history of earlier states \"\"\"+\"\\n\"+\"\"\"\n",
    "The utility function depends on a sequence of states and actions, or an environment history, not a single state. \"\"\"+\"\\n\"+\"\"\"\n",
    "The reward function is R(s,a,s’) which is the transition from s to s’ through action a \"\"\"+\"\\n\"+\"\"\"\n",
    "\"\"\"+\"\\n\"+\"\"\"\n",
    "This is a MDP which is a sequential decision problem for a fully observable, stochastic environment with a Markovian transition and additive rewards. \"\"\"+\"\\n\"+\"\"\"\n",
    "The solution is called a policy, or π, π(s) is the action recommended by the policy π for state s \"\"\"+\"\\n\"+\"\"\"\n",
    "Policy is measured by the expected utility, so an optimal policy is a policy that yields the highest expected utility. \"\"\"+\"\\n\"+\"\"\"\n",
    "A policy depends on time is called nonstationary, or finite horizon. In our example, we deal with infinite horizon, which is simpler because the agent can behave the same in the same state at different time. \"\"\"+\"\\n\"+\"\"\"\n",
    "To calculate the utility of state, we use additive discounted rewards with a discount factor γ between 0-1, which shows agent’s preference of current rewards over future’s. Close to 0 means the agent wants immediate reward and close 1 means agent wants future rewards.  \"\"\"+\"\\n\"+\"\"\"\n",
    "\"\"\"+\"\\n\"+\"\"\"\n",
    "Why additive discounted rewards make sense? \"\"\"+\"\\n\"+\"\"\"\n",
    "Both human and animals value near-term rewards more \"\"\"+\"\\n\"+\"\"\"\n",
    "If rewards are monetary, its between to get it sooner than later \"\"\"+\"\\n\"+\"\"\"\n",
    "True rewards is uncertain, they may never arrive \"\"\"+\"\\n\"+\"\"\"\n",
    "Agent’s preferences between sequences are stationary, if you prefer one future to another starting tomorrow, then you should still prefer that future if it were to start today.\n",
    "It can remove some infinities. \"\"\"+\"\\n\"+\"\"\"\n",
    "If γ<1 and rewards are bounded by +/-Rmax then by geometric series Uh=Rmax/(1-γ) \"\"\"+\"\\n\"+\"\"\"\n",
    "If the environment contains terminal state and agent is guaranteed to get to one eventually, we will never need to compare infinite sequences with a proper policy \"\"\"+\"\\n\"+\"\"\"\n",
    "Infinite sequences can be compared in terms of the average reward obtained per time step \"\"\"+\"\\n\"+\"\"\"\n",
    "\"\"\"+\"\\n\"+\"\"\"\n",
    "We can compare policies by comparing their expected utilities, the utility of a state is given by the Bellman equation: \"\"\"+\"\\n\"+equation2+\"\\n\"+\"\"\"\n",
    "Another quantity is action-utility function, or the Q function Q(s,a) is the expected utility of taking a given action in a given state: \n",
    "U(s) = max Q(s,a)\n",
    "Bellman equation for Q value:\"\"\"+\"\\n\"+equation3+\"\\n\"+\"\"\"\n",
    "Based on the shaping theorem, To represent MDP, the best way to represet P and R is with sparse 3D tables \n",
    "\n",
    " \"\"\"\n",
    "\n",
    "chapter17_2 =  \"\"\"\n",
    "Four ways to solve MDP: \n",
    "1. Value iteration \"\"\"+\"\\n\"+\"\"\"\n",
    "Based on Bellman equation, if there are n states then there are n Bellman equations. \"\"\"+\"\\n\"+\"\"\"\n",
    "The problem is the equations are nonlinear \"\"\"+\"\\n\"+\"\"\"\n",
    "Can try iterative approach, start with arbitrary initial values for the utilities, calculate the right hand side of the equation, and plug it to the left hand side, updating the utility of each state from the utilities of its neighbors. Keep repeating until reach an equilibrium \"\"\"+\"\\n\"+\"\"\"\n",
    "This is not linear \n",
    "2. Policy iteration \"\"\"+\"\\n\"+\"\"\"\n",
    "Policy evaluation: Give a policy π, calculate Ui = U^πi , which is the utility of each state if πi executes \"\"\"+\"\\n\"+\"\"\"\n",
    "Policy improvement: calculate a new MEU policy πi+1 with one-step look-ahead based in Ui \"\"\"+\"\\n\"+\"\"\"\n",
    "The algorithm terminates when policy improvement step yields no change in the utilities. \"\"\"+\"\\n\"+\"\"\"\n",
    "This is linear \"\"\"+\"\\n\"+\"\"\"\n",
    "In each iteration, we can pick any subset of states and apply either kind of updating which is called asynchronous policy iteration \n",
    "3. Linear programing \"\"\"+\"\\n\"+\"\"\"\n",
    "The basic idea is to consider as variables in the LP the utilities of each state s, noting that the utilities for an optimal policy are the highest utilities attainable that are consistent with the Bellman equations\n",
    "4. Online algorithms \"\"\"+\"\\n\"+\"\"\"\n",
    "Value iteration and policy iteration are offline algorithms which generate optimal solution for a simple agent \"\"\"+\"\\n\"+\"\"\"\n",
    "One solution to the online algorithm is a simplification of the expected min-max with rewards on nonterminal states. \"\"\"+\"\\n\"+\"\"\"\n",
    "Another approach is real-time dynamic programming, for moderate-sized domains like grid worlds. It is not suitable for large domain before explored statins contain few repeated domains, so expect-max tree is better. Also if a reward is sparse, a simple heuristic for frontier nodes is not enough to guide the agent. \n",
    " \"\"\"\n",
    "\n",
    "equation4 = r\"\"\" $V*(s) = maxQ*(s,a)$ \"\"\"\n",
    "equation5 = r\"\"\" $Q*(s,a) = \\sum_s T(s,a,s')[R(s,a,s')+γV*(s')]$ \"\"\"\n",
    "equation6 = r\"\"\" $Vk+1(s) = max\\sum_s T(s,a,s')[R(s,a,s')+γVk(s')]$ \"\"\"\n",
    "equation7 = r\"\"\" $Vπ(s) = \\sum_s T(s,π(s),s')[R(s,π(s),s')+γVπ(s')]$ \"\"\"\n",
    "equation8 = r\"\"\" $πi+1(s) = arg max\\sum_s T(s,π(s),s')[R(s,π(s),s')+γVπ(s')]$ \"\"\"\n",
    "# Lecture notes \n",
    "module8_lecture_notes = \"\"\" \n",
    "Stochastic/Markovian transition model: P(s'|s,a) which is the probability of arriving in state s' given that we are in state s and we selected action a. \"\"\"+\"\\n\"+\"\"\"\n",
    "For this model, the agent has a utility or reward function which can be bounded positive or negative value. \"\"\"+\"\\n\"+\"\"\"\n",
    "MDP is sequencial dicision problem in a fully observable environment with a stochastic transition model that has additive rewards, so we need to specify the utility function on a sequence of states and actions, the agent can receive reward at each time step which is additive, not just at goal state, based on transition from s to s' throught a R(s,a,s') \"\"\"+\"\\n\"+\"\"\"\n",
    "Because MDP are non-determinstic, so we can solve it throught expectimax. \"\"\"+\"\\n\"+\"\"\"\n",
    "We need to define following elements for MDP: \n",
    "1. a set of states S \n",
    "2. a set of actions A \n",
    "3. a transition function T(s,a,s'), probability/model that executiong a in s leading to s': P(s'|s,a) \n",
    "4. a reward function R(s,a,s'), sometimes R(s) or R(s') \n",
    "5. an initial state s0 \n",
    "6. optionally, 1+ terminal states \n",
    "\n",
    "The solution of MDP is the policy that maps a state to an action π(s)=a The same policy executed multiple times may have different reward, so we need to compute expected utility of all paths generated by a policy \"\"\"+\"\\n\"+\"\"\"\n",
    "To give utility of sequences, we will give discount factor γ each time descend a level that\n",
    "1. makes sooner rewards higher utility than later rewards and \n",
    "2. help our algo converge. \n",
    "\n",
    "If the gave last forever with infinite utilities, we can \n",
    "1. like depth-limited-search, terminate eposides after fixed steps \n",
    "2. use 0<γ<1 \n",
    "3. absorbing state and guarantee a terminal state will be met. \n",
    "\n",
    "To solve expectimax search tree, we defines \n",
    "1. The utility of a state s: V(s) is the optimal expected utility in s\"\"\"+\"\\n\"+equation4+\"\"\"\n",
    "2. The utility of a q-state: Q(s,a) is the optimal expected utility taking action a from s \"\"\"+\"\\n\"+equation5+\"\"\"\n",
    "3. Optimal policy π(s) is the optimal action from state s \n",
    "\n",
    "First way to solve MDP is value iteration: \"\"\"+\"\\n\"+\"\"\"\n",
    "For each state V*(s) repeat until convergence, time complexity for each iteration is O(S^2*A) \"\"\"+\"\\n\"+equation6+\"\"\"\n",
    "This and 1 and 2 are bellman equations which can be simplfied as take correct first action and keep being optimal \"\"\"+\"\\n\"+\"\"\"\n",
    "The problem with value iteration is that it is slow, the max at each state rarely change and policy converge before values. \"\"\"+\"\\n\"+\"\"\"\n",
    "Contraction is part of the proof of convergence for value iteration algo\"\"\"+\"\\n\"+\"\"\"\n",
    "\"\"\"+\"\\n\"+\"\"\"\n",
    "Second way to slove MDP is policy iteration: \"\"\"+\"\\n\"+\"\"\"\n",
    "We will first compute the utility of a state under a fixed(non-optimal) policy until convergence, time complexity for each iteration os O(s^2), the bellman equation now becomes \"\"\"+equation7+\"\\n\"+\"\"\"\n",
    "Then update policy using one-step-look-ahead/bellman with converged utilities. Repeat steps until policy converges. \"\"\"+\"\\n\"+equation8+\"\\n\"+\"\"\" \n",
    "\n",
    " \"\"\"\n",
    "\n",
    "\n",
    "# Definitions of concepts from Module 8.\n",
    "# You can define any bolded term in the textbook, \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",
    "\"policy\":\"possible actions for each state\",\n",
    "\"utility function\" : \"total of discounted rewards or just rewards\",\n",
    "\"expected utility\" : \"your definition here\",\n",
    "\"etc.\": \"your definition here\",\n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "elCCgY64spuq"
   },
   "source": [
    "## Preview of your notes for Module 8\n",
    "\n",
    "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 121,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 3003
    },
    "id": "gYYeNcdM_maE",
    "outputId": "cb48919c-e830-422b-a3cb-b5d921884cb6"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 8: Markov Decision Processes\n",
       "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
       " \n",
       "The agents has some available actions “a” and P(s) to possible states “s”.\n",
       "\n",
       "Transition model P(s’|s,a) the probability that action a in state s reaches state s’ \n",
       "\n",
       "Decision theory deals with choosing among actions based on the desirability of their immediate outcomes, which means the environment is assumed to be episodic \n",
       "\n",
       "Utility function U(s) assign a single number to express the desirability of a state \n",
       "\n",
       "The expected utility of an action EU(a) is just the average utility value of the outcomes \n",
       " $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(RESULT(a)=s')U(s')$ \n",
       "\n",
       " The principle of maximum expected utility (MEU): a rational agent should choose that action that maximizes the agent’s expected utility: action = argmax EU(a) \n",
       "\n",
       "However, an agent may not know human’s true utility function, so decision theory is just a basic math framework to define AI problem not a panacea. \n",
       " \n",
       "\n",
       "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
       " \n",
       "The agent’s preference \n",
       "\n",
       "1.  A ≻ B the agent prefers A over B \n",
       "2.  A ∼ B the agent is indifferent between them \n",
       "\n",
       "We think of outcomes for every action as a lottery and there are 6 axioms of utility theory about preferences \n",
       "\n",
       "Orderability: a rational agent cannot refuse to decide, it can only prefer one or indifferent \n",
       "\n",
       "Exactly one of (A ≻ B), (B ≻ A), or (A ∼ B) holds. \n",
       "\n",
       "Transitivity: \n",
       "\n",
       "(A ≻ B) ∧ (B ≻ C) ⇒ (A ≻ C) \n",
       "\n",
       "Continuity: if B is between A and C in preference, then there is some probability P that the rational agent will be indifferent between getting B for sure and the lottery that yields A with probability p and C with probability 1-p \n",
       "\n",
       "A ≻ B ≻ C ⇒ ∃ p  [p,A; 1 − p,C] ∼ B \n",
       "\n",
       "Substitutability: if an agent is indifferent between two lotteries A,B then it is indifferent between two more lotteries that are the same except B is substituted for A \n",
       "\n",
       "A ∼ B ⇒ [p,A; 1 − p,C] ∼ [p,B; 1 − p,C]  can also change ~ to ≻ \n",
       "\n",
       "Monotonicity: if two lottery has outcomes A and B, if an agent prefers A to B, then it mush prefer the lottery that has a higher probability for A \n",
       "\n",
       "A ≻ B ⇒ (p > q   ⇔   [p,A; 1 − p,B] ≻ [q,A; 1 − q,B]) \n",
       "\n",
       "Decomposability: compound lotteries can be reduced to simpler ones using the law of probability, no gambling \n",
       "\n",
       "The 6 axions derive following additional  consequences: \n",
       "\n",
       "Existence of utility function: there exists U such that  \n",
       "\n",
       "U(A) > U(B)   ⇔   A ≻ B and U(A) = U(B)   ⇔   A ∼ B \n",
       "\n",
       "The agent’s behavior will not change if U′(S) = aU(S) + b \n",
       "\n",
       "Expected utility of a lottery: is the sum of the probability of each outcome times the utility of that outcome \n",
       "\n",
       "U([p1, S1;…; pn, Sn]) =ΣpiU(Si) \n",
       "\n",
       " \n",
       "\n",
       "## AIMA Chapter 16.3 Utility Functions\n",
       " \n",
       "If we want to build AI that helps a human to make decision, we must figure out human’s utility function. The process is called preference elicitation which involves listing choices and use the preference to derive utility function.  \n",
       "\n",
       "Normalized utilities: use a scale u⊥ = 0 u⊤ = 1, the agent will choose between S, a particular prize, and lottery [p, u⊤; (1 − p), u⊥], p is adjusted until the agent is indifferent S and lottery. Once this is done for each prize, the utilities for all lotteries involving those prizes are determined \n",
       "\n",
       "One value to represent people’s life is micromort, which is a million chance of death. \n",
       "\n",
       "Another measure is QALU, or quality adjusted life year. People are willing to accept a shorter life expectancy to avoid a disability. \n",
       "\n",
       "\n",
       "\n",
       "Utility of money: \n",
       "\n",
       "1. EMV is the expected monetary value \n",
       "2. The utility of money was proportional to the log of the amount based on Grayson study. most people have a utility function that is concave for positive wealth, or risk averse, people prefer a sure thing with a payoff that is less than the EMV of a gamble. Looking at the positive part of the curve, U(L) < U(SEMV (L)).\n",
       "3. However, in the negative wealth, people tend to be risk seeking.\n",
       "4. The difference between the EMV and its certainty equivalent is called insurance premium, which insurance industry believes the premium is positive.\n",
       "5. Linear curve is risk neutral \n",
       "\n",
       "In reality, we usually under estimate. \n",
       "\n",
       "A rational agent should act based on a normative theory, but actual agent acts with descriptive theory, explained by certainty effect that people are attracted to gains that are certain. People dislike ambiguity aversion (1/3 vs 2/3), and like framing effect (90% survival rate vs 10% death rate), prefer anchoring effect ($200 vs $50 with relative utility judgement) \n",
       " \n",
       "\n",
       "## AIMA Chapter 17.1 Sequential Decision Problems\n",
       " \n",
       "Several rules: \n",
       "\n",
       "The environment is fully observable \n",
       "\n",
       "But not deterministic \n",
       "\n",
       "If the agent bumps into a wall, it stays in the same square \n",
       "\n",
       "The transition model describes the outcome of each action in each state. Because the outcome is stochastic, T(s,a,s’) represents the probability of reaching state s’ if action a is done in state s. \n",
       "\n",
       "Assume the transitions are Markovian, the probability of reaching s’ from s depends only on s and not on the history of earlier states \n",
       "\n",
       "The utility function depends on a sequence of states and actions, or an environment history, not a single state. \n",
       "\n",
       "The reward function is R(s,a,s’) which is the transition from s to s’ through action a \n",
       "\n",
       "\n",
       "\n",
       "This is a MDP which is a sequential decision problem for a fully observable, stochastic environment with a Markovian transition and additive rewards. \n",
       "\n",
       "The solution is called a policy, or π, π(s) is the action recommended by the policy π for state s \n",
       "\n",
       "Policy is measured by the expected utility, so an optimal policy is a policy that yields the highest expected utility. \n",
       "\n",
       "A policy depends on time is called nonstationary, or finite horizon. In our example, we deal with infinite horizon, which is simpler because the agent can behave the same in the same state at different time. \n",
       "\n",
       "To calculate the utility of state, we use additive discounted rewards with a discount factor γ between 0-1, which shows agent’s preference of current rewards over future’s. Close to 0 means the agent wants immediate reward and close 1 means agent wants future rewards.  \n",
       "\n",
       "\n",
       "\n",
       "Why additive discounted rewards make sense? \n",
       "\n",
       "Both human and animals value near-term rewards more \n",
       "\n",
       "If rewards are monetary, its between to get it sooner than later \n",
       "\n",
       "True rewards is uncertain, they may never arrive \n",
       "\n",
       "Agent’s preferences between sequences are stationary, if you prefer one future to another starting tomorrow, then you should still prefer that future if it were to start today.\n",
       "It can remove some infinities. \n",
       "\n",
       "If γ<1 and rewards are bounded by +/-Rmax then by geometric series Uh=Rmax/(1-γ) \n",
       "\n",
       "If the environment contains terminal state and agent is guaranteed to get to one eventually, we will never need to compare infinite sequences with a proper policy \n",
       "\n",
       "Infinite sequences can be compared in terms of the average reward obtained per time step \n",
       "\n",
       "\n",
       "\n",
       "We can compare policies by comparing their expected utilities, the utility of a state is given by the Bellman equation: \n",
       " $U(s) = max\\sum_s P(s'|s,a)[R(s,a,s')+γU(s')]$ \n",
       "\n",
       "Another quantity is action-utility function, or the Q function Q(s,a) is the expected utility of taking a given action in a given state: \n",
       "U(s) = max Q(s,a)\n",
       "Bellman equation for Q value:\n",
       " $Q(s,a) = max\\sum_s P(s'|s,a)[R(s,a,s')+γmaxQ(s',a')]$ \n",
       "\n",
       "Based on the shaping theorem, To represent MDP, the best way to represet P and R is with sparse 3D tables \n",
       "\n",
       " \n",
       "\n",
       "## AIMA Chapter 17.2 Algorithms for MDPs\n",
       "\n",
       "Four ways to solve MDP: \n",
       "1. Value iteration \n",
       "\n",
       "Based on Bellman equation, if there are n states then there are n Bellman equations. \n",
       "\n",
       "The problem is the equations are nonlinear \n",
       "\n",
       "Can try iterative approach, start with arbitrary initial values for the utilities, calculate the right hand side of the equation, and plug it to the left hand side, updating the utility of each state from the utilities of its neighbors. Keep repeating until reach an equilibrium \n",
       "\n",
       "This is not linear \n",
       "2. Policy iteration \n",
       "\n",
       "Policy evaluation: Give a policy π, calculate Ui = U^πi , which is the utility of each state if πi executes \n",
       "\n",
       "Policy improvement: calculate a new MEU policy πi+1 with one-step look-ahead based in Ui \n",
       "\n",
       "The algorithm terminates when policy improvement step yields no change in the utilities. \n",
       "\n",
       "This is linear \n",
       "\n",
       "In each iteration, we can pick any subset of states and apply either kind of updating which is called asynchronous policy iteration \n",
       "3. Linear programing \n",
       "\n",
       "The basic idea is to consider as variables in the LP the utilities of each state s, noting that the utilities for an optimal policy are the highest utilities attainable that are consistent with the Bellman equations\n",
       "4. Online algorithms \n",
       "\n",
       "Value iteration and policy iteration are offline algorithms which generate optimal solution for a simple agent \n",
       "\n",
       "One solution to the online algorithm is a simplification of the expected min-max with rewards on nonterminal states. \n",
       "\n",
       "Another approach is real-time dynamic programming, for moderate-sized domains like grid worlds. It is not suitable for large domain before explored statins contain few repeated domains, so expect-max tree is better. Also if a reward is sparse, a simple heuristic for frontier nodes is not enough to guide the agent. \n",
       " \n",
       "\n",
       "## Module 8 Lecture Notes\n",
       " \n",
       "Stochastic/Markovian transition model: P(s'|s,a) which is the probability of arriving in state s' given that we are in state s and we selected action a. \n",
       "\n",
       "For this model, the agent has a utility or reward function which can be bounded positive or negative value. \n",
       "\n",
       "MDP is sequencial dicision problem in a fully observable environment with a stochastic transition model that has additive rewards, so we need to specify the utility function on a sequence of states and actions, the agent can receive reward at each time step which is additive, not just at goal state, based on transition from s to s' throught a R(s,a,s') \n",
       "\n",
       "Because MDP are non-determinstic, so we can solve it throught expectimax. \n",
       "\n",
       "We need to define following elements for MDP: \n",
       "1. a set of states S \n",
       "2. a set of actions A \n",
       "3. a transition function T(s,a,s'), probability/model that executiong a in s leading to s': P(s'|s,a) \n",
       "4. a reward function R(s,a,s'), sometimes R(s) or R(s') \n",
       "5. an initial state s0 \n",
       "6. optionally, 1+ terminal states \n",
       "\n",
       "The solution of MDP is the policy that maps a state to an action π(s)=a The same policy executed multiple times may have different reward, so we need to compute expected utility of all paths generated by a policy \n",
       "\n",
       "To give utility of sequences, we will give discount factor γ each time descend a level that\n",
       "1. makes sooner rewards higher utility than later rewards and \n",
       "2. help our algo converge. \n",
       "\n",
       "If the gave last forever with infinite utilities, we can \n",
       "1. like depth-limited-search, terminate eposides after fixed steps \n",
       "2. use 0<γ<1 \n",
       "3. absorbing state and guarantee a terminal state will be met. \n",
       "\n",
       "To solve expectimax search tree, we defines \n",
       "1. The utility of a state s: V(s) is the optimal expected utility in s\n",
       " $V*(s) = maxQ*(s,a)$ \n",
       "2. The utility of a q-state: Q(s,a) is the optimal expected utility taking action a from s \n",
       " $Q*(s,a) = \\sum_s T(s,a,s')[R(s,a,s')+γV*(s')]$ \n",
       "3. Optimal policy π(s) is the optimal action from state s \n",
       "\n",
       "First way to solve MDP is value iteration: \n",
       "\n",
       "For each state V*(s) repeat until convergence, time complexity for each iteration is O(S^2*A) \n",
       " $Vk+1(s) = max\\sum_s T(s,a,s')[R(s,a,s')+γVk(s')]$ \n",
       "This and 1 and 2 are bellman equations which can be simplfied as take correct first action and keep being optimal \n",
       "\n",
       "The problem with value iteration is that it is slow, the max at each state rarely change and policy converge before values. \n",
       "\n",
       "Contraction is part of the proof of convergence for value iteration algo\n",
       "\n",
       "\n",
       "\n",
       "Second way to slove MDP is policy iteration: \n",
       "\n",
       "We will first compute the utility of a state under a fixed(non-optimal) policy until convergence, time complexity for each iteration os O(s^2), the bellman equation now becomes  $Vπ(s) = \\sum_s T(s,π(s),s')[R(s,π(s),s')+γVπ(s')]$ \n",
       "\n",
       "Then update policy using one-step-look-ahead/bellman with converged utilities. Repeat steps until policy converges. \n",
       " $πi+1(s) = arg max\\sum_s T(s,π(s),s')[R(s,π(s),s')+γVπ(s')]$ \n",
       " \n",
       "\n",
       " \n",
       "\n",
       "## Module 8 Definitions\n",
       "* **Policy** - possible actions for each state\n",
       "* **Utility function** - total of discounted rewards or just rewards\n",
       "* **Expected utility** - your definition here\n",
       "* **Etc.** - your definition here\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "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))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "9xRbdqDox2zD"
   },
   "source": [
    "#Module 9 - Reinforcement Learning"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "metadata": {
    "id": "DpBvu7EMx7sy"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA Section 17.3 “Bandit Problems”\n",
    "chapter17_3 =  \"\"\" \n",
    "The n-armed bandit is a formal model for real problems like deciding n possible investments. \"\"\"+\"\\n\"+\"\"\"\n",
    "The optimal policy does not settle on the best arm in the long run, it could settle on a suboptimal arm  \"\"\"+\"\\n\"+\"\"\"\n",
    "To define bandit problem: \"\"\"+\"\\n\"+\"\"\"\n",
    "1. Each arm Mi is a MDP with only 1 possible action ai. The arm defines a distribution over sequences of rewards Ri,0, R,i,1,…, each Ri,t is random. \n",
    "2. The state space is the cartesian product S=S1*…*Sn \n",
    "3. One-arm bandit is when the result is equal to one arm M that produce R0, R1, R2… and cost λ for each pull\n",
    "4. If you pull arm for T times, the stopping time is T \n",
    "5. Gittin index of M provides a very simple optimal policy for any bandit probem: pull the arm that has the highest Gittin index then update the Gittin indices \n",
    "6. First decision takes O(n), latter decision cost O(1) \n",
    "7. Simplest and best known bandit problem is the Bernoulli bandit, where each arm has reward of 0 or 1. It also has a exploration bonus for arms that only been tried for a few times \n",
    " \"\"\"\n",
    "\n",
    "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
    "chapter22_1 =  \"\"\" \n",
    "RL agent interacts with the environment and receive rewards based on its performance. For example, with MDP, the agent does not know the transition model or reward function, the agent needs to act to learn. \"\"\"+\"\\n\"+\"\"\"\n",
    "Providing a reward to the agent is easier than give it example of how to perform because the reward function is concise and easy to define. We also don’t have to give correct action in any situation. \"\"\"+\"\\n\"+\"\"\"\n",
    "A sparse rewards is win/loss because it has no informative reward signal. Some examples are chess and racing.\"\"\"+\"\\n\"+\"\"\"\n",
    "We will learn five category of algorithms\"\"\"+\"\\n\"+\"\"\"\n",
    "1. Model-based reinforcement learning: the agent uses a transition model of the environment to help interpret the reward signals and make decision. The transition model may be known like chess rule, or unknown. \n",
    "2. Model-free reinforcement learning: the agent neither knows nor learns a transition model. It learns a more direct way to behave. \n",
    "Action-utility learning, like Q-learning, which denote the sum of rewards from state s onward if action a is taken. The agent choose action with the highest Q value. \n",
    "Policy-search: the agent learns a policy π that maps states to actions like reflex agent. \n",
    "3. Passive reinforcement learning: agent’s policy is fixed and the task is to learn the utilities of states. \n",
    "4. Active reinforcement learning: agent also need to figure out what to do through exploration. An agent must experience as much as possible of the environment to learn how to behave. \n",
    "5. Inductive learning: agent can learn faster form its experiences with approaches like providing intermediate pseudo rewards. \n",
    "6. Apprenticeship learning: training a learning agent using demonstrations instead of reward signals. \n",
    "\n",
    " \"\"\"\n",
    "chapter22_2 =  \"\"\" \n",
    "Start with a simple case where a fully observable environment with a small number of actions and states and fixed policy π. The agent try to learn the utility function U is called passive learning agent. \"\"\"+\"\\n\"+\"\"\"\n",
    "Passive learning task is similar to policy evaluation task, but the difference is the passive learning agent does not know the transition model P or reward function R. \"\"\"+\"\\n\"+\"\"\"\n",
    "The agent will execute a set of trails using policy π \"\"\"+\"\\n\"+\"\"\"\n",
    "The utility is defined to be the expected sum of discounted rewards obtained if policy π is followed \"\"\"+\"\\n\"+\"\"\"\n",
    "Direct utility estimation: the utility of a state is defined as the expected total reward from that state onward. This reduced reinforcement learning to a standard supervised learning problem. It ignores an important constraint that the utility of a state is determined by the reward and expected utility of the successor states. It obeys the Bellman equations for a fixed policy \"\"\"+\"\\n\"+\"\"\"\n",
    "Adaptive dynamic programming: takes advantage of the constraints among the utilities of states through learning the transition model and solving MDP through DP. For a passive learning agent, this means insert learned transition model and observed rewards into above equation to calculate the utilities of the states. \"\"\"+\"\\n\"+\"\"\"\n",
    "Temporal-difference learning: another way is to use the observed transitions to adjust the utilities of the observed stats so that they agree with the constraint equations. Below is the TD equation. It does not learn as fast as the ADP agent but it’s much simpler and require less computation. α is the learning rate parameter. TD does not need a transition model to perform update. \"\"\"+\"\\n\"+\"\"\"\n",
    "ADP and TD are very similar, both try to make adjustment to the utility function and have each state agree with successors. The difference is that TD adjust a state to agree with its observed successor but ADP agree with all successors. This difference disappears when the effect of TD adjustments are averaged over a large number of transactions. Another difference is that TD makes a single adjustment per transition and ADP makes as many as it needs. From TD’s view, each adjustment ADP make is a result of pseudo-experience generated by simulating the current transition model. TD agent can also generate a large number of imaginary transitions, so the resulting utility estimates will approximate more and more closely to ADP. \"\"\"+\"\\n\"+\"\"\"\n",
    "One can also use a heuristic to rank possible adjustments and carry out the important ones. For example the prioritized sweeping heuristic prefers to make adjustments to stats whose successors have just undergone a large adjustment. With these heuristics approximate ADP can learn almost as fast as full ADP. They can then handle state spaces are too large for full ADP \"\"\"+\"\\n\"+\"\"\"\n",
    " \"\"\"\n",
    "chapter22_3 =  \"\"\" \n",
    "Passive learning agent has a fixed policy that determines its behavior, but active learning agent decide what actions to take. \"\"\"+\"\\n\"+\"\"\"\n",
    "First the agent need to learn a complete transition model with outcome probabilities for all actions, next the agent has a choice of actions and the utilities it needs to learn are those defined by the optimal policy. So the agent need to obtain the utility function U using the value iteration or policy iteration algorithms. Finally with the utility function the agent can extract the optimal action by 1-step-look-ahead to pick the action maximizing the expected utility. \"\"\"+\"\\n\"+\"\"\"\n",
    "\"\"\"+\"\\n\"+\"\"\" \n",
    "Exploration \"\"\"+\"\\n\"+\"\"\"\n",
    "1. Greedy agent greedily takes the actin that it currently believes to be optimal \n",
    "2. A GLIE (greedy in the limit of infinite exploration” scheme must try each action in each state unbounded number of times to avoid an optimal action being missed. The most simple one is to have the agent choose a random action at time step t with probability 1/t, otherwise follow the greedy policy. This is slow but will eventually converge. A better approach is to add some weight to actions that agent has not tried. Here f is the exploration function \n",
    "\n",
    "Safe exploration \"\"\"+\"\\n\"+\"\"\"\n",
    "1. Not all actions are safe and some are irreversible. The worst case is entering an absorbing state where no actions have effect and no rewards are given. \"\"\"+\"\\n\"+\"\"\"\n",
    "2. We cannot afford to enter these bad states in practical settings so a better idea is to choose a policy works reasonably well and close to true model. There are three math approaches \n",
    "Bayesian reinforcement learning: which assumes a prior probability P(h) over h about the true model. When agent decides to stop learning, the optimal policy is the one with highest utility \n",
    "\n",
    "Robust control theory allows a set of possible models H without assigning probabilities and defines an optimal robust policy which gives the best outcome in the worst case over H. It is like the minmax solution where adversary pick the worst possible result. The issue is the result is too conservative, so human can pre set a serious of actions so the system can act reasonably from the start and learn to improve. Human can also write down constraints on what a system can do and a program outside the learning system can enforce those constraints. \"\"\"+\"\\n\"+\"\"\"\n",
    "Temporal-difference q-learnin \"\"\"+\"\\n\"+\"\"\"\n",
    "It does not need a transition model P either for learning or for action selection. It also cannot look into the future, so its hard when rewards are hard and long actions sequences need to be constructed to reach them.\"\"\"+\"\\n\"+\"\"\"\n",
    "Q-learning is an off-policy algo but SARSA is an on-policy algo.\"\"\"+\"\\n\"+\"\"\"\n",
    "\"\"\"\n",
    "chapter22_4 =  \"\"\" \n",
    "Utility functions and Q-functions work for state space up tp 10^6, which is too slow for real-world environments. \"\"\"+\"\\n\"+\"\"\"\n",
    "We can also use function approximation to approximate the true utility function or Q-function. \"\"\"+\"\\n\"+\"\"\"\n",
    "Approximating direct utility function - It generates trajectories in the state space and extract the sum of rewards for each state. The state and sum of rewards received form a example for supervised learning. For reinforcement learning, its better to use an online learning algorithm that updates the parameter after each trial. \"\"\"+\"\\n\"+\"\"\"\n",
    "\n",
    "Approximating temporal-difference learning\"\"\"+\"\\n\"+\"\"\"\n",
    "1. We need to adjust the parameters to reduce temporal difference between successive states. \n",
    "2. When the function approximator is linear the update rule can converge close to true function for passive TD learning.\n",
    "3. For active learning and nonlinear functions like neural networks it does not work. The parameters can go to infinity. There is another problem called catastrophic forgetting when the agent has learned too well. One solution is experience replay where the learning algorithm can retain trajectories and replay to ensure its value function is still accurate to state space that it does not visit. \n",
    "4. For model-based reinforcement learning, function approximation can be helpful for meaning a model of the environment. Learning a model from an observable environment is a supervised learning problem. \n",
    "5. For a partially observable environment, the learning problem is harder because the next percept is not a label for the state prediction. \n",
    "\n",
    "Deep reinforcement learning \"\"\"+\"\\n\"+\"\"\"\n",
    "1. There may be no good linear function to approximate utility function and we may not invent necessary features in new domains, so researchers explored more complex, nonlinear function approximators, like deep neural networks.\n",
    "2. Deep RL still have issues like hard to get good performance and the trained system may be have unpredictably if environment differ from the training data. \n",
    "\n",
    "Reward shaping - This involves supplying agent with additional rewards for making progress.\n",
    "\n",
    "Hierarchical reinforcement learning - Another way to solve long action sequence is to break them up into smaller pieces until the actin sequence are short enough to make learning easy. \n",
    "\n",
    " \"\"\"\n",
    "chapter22_5 =  \"\"\" The idea is to keep adjusting the policy until performance does not improve.\n",
    "\"\"\"\n",
    "\n",
    "equation9=r\"\"\" $ sample=R(s,π(s),s')+ γVπ(s')$ \"\"\"\n",
    "equation10 = r\"\"\" $Vπ(s) = (1-α)Vπ(s)+(α)sample]$ \"\"\"\n",
    "equation11 = \"\"\" $Qk+1(s,a) = \\sum_s T(s,a,s')[R(s,a,s')+γmaxQk(s',a')]$ \"\"\"\n",
    "equation12 = \"\"\" $Q(s,a) = R(s,a,s')+γmax f(Q(s',a'),N(s',a'))$ \"\"\"\n",
    "# Lecture notes \n",
    "module9_lecture_notes = \"\"\" \n",
    "Solving MDP is like offline planning because you do not actually play the game, you just know the details and determine all quantities through computation. \"\"\"+\"\\n\"+\"\"\"\n",
    "Reinforcement learning involves below concepts:\"\"\"+\"\\n\"+\"\"\"\n",
    "1. Exploration which means you have to try unknown action to get information \n",
    "2. Exploitation which means you have to use what you know eventually \n",
    "3. Regret which means you may make mistakes even after learning \n",
    "4. Sampling wihch means you need to try things repeatedly \n",
    "5. Difficulty which means learning is harder than solving MDP \n",
    "\n",
    "In reinforcement learning, the agent will receive feedback in form of rewards. Its utility is defined by the reward function and must learn to maximiaze rewards based on observed sample of outcomes. \"\"\"+\"\\n\"+\"\"\"\n",
    "Compared with MDP it still has states S, actions A, model T, reward function R, looking for policy π, but does not know T or R. \"\"\"+\"\\n\"+\"\"\"\n",
    "\"\"\"+\"\\n\"+\"\"\"\n",
    "Model-Based Learing: learn the model based on experiences and solve for values assuming learned model were correct. \"\"\"+\"\\n\"+\"\"\"\n",
    "1. count outcomes s' for each s, estimate T, and discover R when experience (s,a,s') \n",
    "2. solved the learned MDP as before \n",
    "\n",
    "Passive reinforcement learning: input a π, witout T and R learn the state values. This is online learning. \"\"\"+\"\\n\"+\"\"\"\n",
    "\"\"\"+\"\\n\"+\"\"\"\n",
    "Direct evalueation: compute values for each state under π by average observed sample values \"\"\"+\"\\n\"+\"\"\"\n",
    "1. Pro is it does not need knowledge for T, R and compute correct average values \n",
    "2. Con is each state must be learned separately which takes long time and waste state connections \n",
    "\n",
    "Temporal Difference (TD) Learing: learn from evey experience. Decreasing learning rate can give converging averages and bigger α trust estimates more \"\"\"+\"\\n\"+\"\"\"\n",
    "1. Sample of V(s): \"\"\"+\"\\n\"+equation9+\"\"\"\n",
    "2. Update to V(s): \"\"\"+\"\\n\"+equation10+\"\"\"\n",
    "3. TD is a model free way to evalue policy, like Bellman updates, we can try to learn Q values and make action selection model free\n",
    "\n",
    "Active reinforcement learning: without T and R, learner make choices. This is also online learning \"\"\"+\"\\n\"+\"\"\"\n",
    "\"\"\"+\"\\n\"+\"\"\"\n",
    "Q-Value iteration: start with Q0(s,a)=0 which is right, given Qk, calculate the depth k+1 q-values for all q-states: \"\"\"+\"\\n\"+equation11+\"\"\"\n",
    "This coverges to optimal policy even if you are acting suboptimally, but you have to explore enough, eventually make the learning rate small enough but not decrease too fast \"\"\"+\"\\n\"+\"\"\"\n",
    "\"\"\"+\"\\n\"+\"\"\"\n",
    "To explore, we can do random: ε act radomly, ow current policy, but the problems is although eventually explore the space, keey thrashing around. We can lower ε over time or use a exploration functions.\n",
    "If an agent's explore function values curiositym N(s,a) will be low. Q learning can learn the optimal Q-function through off policy learningand not executing the optimal policy. \n",
    "Q learning will be come: \"\"\"+\"\\n\"+equation12+\"\"\"\n",
    "\"\"\"+\"\\n\"+\"\"\"\n",
    "Regret is a measure of your total mistake cost which includes the different between your expected rewards and optimal rewards. It quantifies the relative goodness of exploration procedures\"\"\"+\"\\n\"+\"\"\"\n",
    "Basic Q learning keep a table of all q-values, which is too much to hold in memory. We can generalize it by learning small number of training states from experience and generalize that to new similar situations. \"\"\"+\"\\n\"+\"\"\"\n",
    "Q(s,a)=w1f1(s,a)+w2f2(s,a)+...+wnfn(s,a) \"\"\"+\"\\n\"+\"\"\"\n",
    "There might be cases that states with similar features but different values.\n",
    " \"\"\"\n",
    "\n",
    "# Each definition should be at most 25 words long.\n",
    "module9_definitions = {\n",
    "\"term\" : \"your definition here\",\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 123,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 2825
    },
    "id": "ydOK__lwWgdp",
    "outputId": "3172643b-b617-459b-dca0-4f71b5bbaf49"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 9: Reinforcement Learning\n",
       "## AIMA Chapter 17.3 Bandit Problems\n",
       " \n",
       "The n-armed bandit is a formal model for real problems like deciding n possible investments. \n",
       "\n",
       "The optimal policy does not settle on the best arm in the long run, it could settle on a suboptimal arm  \n",
       "\n",
       "To define bandit problem: \n",
       "\n",
       "1. Each arm Mi is a MDP with only 1 possible action ai. The arm defines a distribution over sequences of rewards Ri,0, R,i,1,…, each Ri,t is random. \n",
       "2. The state space is the cartesian product S=S1*…*Sn \n",
       "3. One-arm bandit is when the result is equal to one arm M that produce R0, R1, R2… and cost λ for each pull\n",
       "4. If you pull arm for T times, the stopping time is T \n",
       "5. Gittin index of M provides a very simple optimal policy for any bandit probem: pull the arm that has the highest Gittin index then update the Gittin indices \n",
       "6. First decision takes O(n), latter decision cost O(1) \n",
       "7. Simplest and best known bandit problem is the Bernoulli bandit, where each arm has reward of 0 or 1. It also has a exploration bonus for arms that only been tried for a few times \n",
       " \n",
       "\n",
       "## AIMA Chapter 22.1 Learning from Rewards\n",
       " \n",
       "RL agent interacts with the environment and receive rewards based on its performance. For example, with MDP, the agent does not know the transition model or reward function, the agent needs to act to learn. \n",
       "\n",
       "Providing a reward to the agent is easier than give it example of how to perform because the reward function is concise and easy to define. We also don’t have to give correct action in any situation. \n",
       "\n",
       "A sparse rewards is win/loss because it has no informative reward signal. Some examples are chess and racing.\n",
       "\n",
       "We will learn five category of algorithms\n",
       "\n",
       "1. Model-based reinforcement learning: the agent uses a transition model of the environment to help interpret the reward signals and make decision. The transition model may be known like chess rule, or unknown. \n",
       "2. Model-free reinforcement learning: the agent neither knows nor learns a transition model. It learns a more direct way to behave. \n",
       "Action-utility learning, like Q-learning, which denote the sum of rewards from state s onward if action a is taken. The agent choose action with the highest Q value. \n",
       "Policy-search: the agent learns a policy π that maps states to actions like reflex agent. \n",
       "3. Passive reinforcement learning: agent’s policy is fixed and the task is to learn the utilities of states. \n",
       "4. Active reinforcement learning: agent also need to figure out what to do through exploration. An agent must experience as much as possible of the environment to learn how to behave. \n",
       "5. Inductive learning: agent can learn faster form its experiences with approaches like providing intermediate pseudo rewards. \n",
       "6. Apprenticeship learning: training a learning agent using demonstrations instead of reward signals. \n",
       "\n",
       " \n",
       "\n",
       "## AIMA Chapter 22.2 Passive Reinforcement Learning\n",
       " \n",
       "Start with a simple case where a fully observable environment with a small number of actions and states and fixed policy π. The agent try to learn the utility function U is called passive learning agent. \n",
       "\n",
       "Passive learning task is similar to policy evaluation task, but the difference is the passive learning agent does not know the transition model P or reward function R. \n",
       "\n",
       "The agent will execute a set of trails using policy π \n",
       "\n",
       "The utility is defined to be the expected sum of discounted rewards obtained if policy π is followed \n",
       "\n",
       "Direct utility estimation: the utility of a state is defined as the expected total reward from that state onward. This reduced reinforcement learning to a standard supervised learning problem. It ignores an important constraint that the utility of a state is determined by the reward and expected utility of the successor states. It obeys the Bellman equations for a fixed policy \n",
       "\n",
       "Adaptive dynamic programming: takes advantage of the constraints among the utilities of states through learning the transition model and solving MDP through DP. For a passive learning agent, this means insert learned transition model and observed rewards into above equation to calculate the utilities of the states. \n",
       "\n",
       "Temporal-difference learning: another way is to use the observed transitions to adjust the utilities of the observed stats so that they agree with the constraint equations. Below is the TD equation. It does not learn as fast as the ADP agent but it’s much simpler and require less computation. α is the learning rate parameter. TD does not need a transition model to perform update. \n",
       "\n",
       "ADP and TD are very similar, both try to make adjustment to the utility function and have each state agree with successors. The difference is that TD adjust a state to agree with its observed successor but ADP agree with all successors. This difference disappears when the effect of TD adjustments are averaged over a large number of transactions. Another difference is that TD makes a single adjustment per transition and ADP makes as many as it needs. From TD’s view, each adjustment ADP make is a result of pseudo-experience generated by simulating the current transition model. TD agent can also generate a large number of imaginary transitions, so the resulting utility estimates will approximate more and more closely to ADP. \n",
       "\n",
       "One can also use a heuristic to rank possible adjustments and carry out the important ones. For example the prioritized sweeping heuristic prefers to make adjustments to stats whose successors have just undergone a large adjustment. With these heuristics approximate ADP can learn almost as fast as full ADP. They can then handle state spaces are too large for full ADP \n",
       "\n",
       " \n",
       "\n",
       "## AIMA Chapter 22.3 Active Reinforcement Learning\n",
       " \n",
       "Passive learning agent has a fixed policy that determines its behavior, but active learning agent decide what actions to take. \n",
       "\n",
       "First the agent need to learn a complete transition model with outcome probabilities for all actions, next the agent has a choice of actions and the utilities it needs to learn are those defined by the optimal policy. So the agent need to obtain the utility function U using the value iteration or policy iteration algorithms. Finally with the utility function the agent can extract the optimal action by 1-step-look-ahead to pick the action maximizing the expected utility. \n",
       "\n",
       "\n",
       " \n",
       "Exploration \n",
       "\n",
       "1. Greedy agent greedily takes the actin that it currently believes to be optimal \n",
       "2. A GLIE (greedy in the limit of infinite exploration” scheme must try each action in each state unbounded number of times to avoid an optimal action being missed. The most simple one is to have the agent choose a random action at time step t with probability 1/t, otherwise follow the greedy policy. This is slow but will eventually converge. A better approach is to add some weight to actions that agent has not tried. Here f is the exploration function \n",
       "\n",
       "Safe exploration \n",
       "\n",
       "1. Not all actions are safe and some are irreversible. The worst case is entering an absorbing state where no actions have effect and no rewards are given. \n",
       "\n",
       "2. We cannot afford to enter these bad states in practical settings so a better idea is to choose a policy works reasonably well and close to true model. There are three math approaches \n",
       "Bayesian reinforcement learning: which assumes a prior probability P(h) over h about the true model. When agent decides to stop learning, the optimal policy is the one with highest utility \n",
       "\n",
       "Robust control theory allows a set of possible models H without assigning probabilities and defines an optimal robust policy which gives the best outcome in the worst case over H. It is like the minmax solution where adversary pick the worst possible result. The issue is the result is too conservative, so human can pre set a serious of actions so the system can act reasonably from the start and learn to improve. Human can also write down constraints on what a system can do and a program outside the learning system can enforce those constraints. \n",
       "\n",
       "Temporal-difference q-learnin \n",
       "\n",
       "It does not need a transition model P either for learning or for action selection. It also cannot look into the future, so its hard when rewards are hard and long actions sequences need to be constructed to reach them.\n",
       "\n",
       "Q-learning is an off-policy algo but SARSA is an on-policy algo.\n",
       "\n",
       "\n",
       "\n",
       "## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n",
       " \n",
       "Utility functions and Q-functions work for state space up tp 10^6, which is too slow for real-world environments. \n",
       "\n",
       "We can also use function approximation to approximate the true utility function or Q-function. \n",
       "\n",
       "Approximating direct utility function - It generates trajectories in the state space and extract the sum of rewards for each state. The state and sum of rewards received form a example for supervised learning. For reinforcement learning, its better to use an online learning algorithm that updates the parameter after each trial. \n",
       "\n",
       "\n",
       "Approximating temporal-difference learning\n",
       "\n",
       "1. We need to adjust the parameters to reduce temporal difference between successive states. \n",
       "2. When the function approximator is linear the update rule can converge close to true function for passive TD learning.\n",
       "3. For active learning and nonlinear functions like neural networks it does not work. The parameters can go to infinity. There is another problem called catastrophic forgetting when the agent has learned too well. One solution is experience replay where the learning algorithm can retain trajectories and replay to ensure its value function is still accurate to state space that it does not visit. \n",
       "4. For model-based reinforcement learning, function approximation can be helpful for meaning a model of the environment. Learning a model from an observable environment is a supervised learning problem. \n",
       "5. For a partially observable environment, the learning problem is harder because the next percept is not a label for the state prediction. \n",
       "\n",
       "Deep reinforcement learning \n",
       "\n",
       "1. There may be no good linear function to approximate utility function and we may not invent necessary features in new domains, so researchers explored more complex, nonlinear function approximators, like deep neural networks.\n",
       "2. Deep RL still have issues like hard to get good performance and the trained system may be have unpredictably if environment differ from the training data. \n",
       "\n",
       "Reward shaping - This involves supplying agent with additional rewards for making progress.\n",
       "\n",
       "Hierarchical reinforcement learning - Another way to solve long action sequence is to break them up into smaller pieces until the actin sequence are short enough to make learning easy. \n",
       "\n",
       " \n",
       "\n",
       "## Module 9 Lecture Notes\n",
       " \n",
       "Solving MDP is like offline planning because you do not actually play the game, you just know the details and determine all quantities through computation. \n",
       "\n",
       "Reinforcement learning involves below concepts:\n",
       "\n",
       "1. Exploration which means you have to try unknown action to get information \n",
       "2. Exploitation which means you have to use what you know eventually \n",
       "3. Regret which means you may make mistakes even after learning \n",
       "4. Sampling wihch means you need to try things repeatedly \n",
       "5. Difficulty which means learning is harder than solving MDP \n",
       "\n",
       "In reinforcement learning, the agent will receive feedback in form of rewards. Its utility is defined by the reward function and must learn to maximiaze rewards based on observed sample of outcomes. \n",
       "\n",
       "Compared with MDP it still has states S, actions A, model T, reward function R, looking for policy π, but does not know T or R. \n",
       "\n",
       "\n",
       "\n",
       "Model-Based Learing: learn the model based on experiences and solve for values assuming learned model were correct. \n",
       "\n",
       "1. count outcomes s' for each s, estimate T, and discover R when experience (s,a,s') \n",
       "2. solved the learned MDP as before \n",
       "\n",
       "Passive reinforcement learning: input a π, witout T and R learn the state values. This is online learning. \n",
       "\n",
       "\n",
       "\n",
       "Direct evalueation: compute values for each state under π by average observed sample values \n",
       "\n",
       "1. Pro is it does not need knowledge for T, R and compute correct average values \n",
       "2. Con is each state must be learned separately which takes long time and waste state connections \n",
       "\n",
       "Temporal Difference (TD) Learing: learn from evey experience. Decreasing learning rate can give converging averages and bigger α trust estimates more \n",
       "\n",
       "1. Sample of V(s): \n",
       " $ sample=R(s,π(s),s')+ γVπ(s')$ \n",
       "2. Update to V(s): \n",
       " $Vπ(s) = (1-α)Vπ(s)+(α)sample]$ \n",
       "3. TD is a model free way to evalue policy, like Bellman updates, we can try to learn Q values and make action selection model free\n",
       "\n",
       "Active reinforcement learning: without T and R, learner make choices. This is also online learning \n",
       "\n",
       "\n",
       "\n",
       "Q-Value iteration: start with Q0(s,a)=0 which is right, given Qk, calculate the depth k+1 q-values for all q-states: \n",
       " $Qk+1(s,a) = \\sum_s T(s,a,s')[R(s,a,s')+γmaxQk(s',a')]$ \n",
       "This coverges to optimal policy even if you are acting suboptimally, but you have to explore enough, eventually make the learning rate small enough but not decrease too fast \n",
       "\n",
       "\n",
       "\n",
       "To explore, we can do random: ε act radomly, ow current policy, but the problems is although eventually explore the space, keey thrashing around. We can lower ε over time or use a exploration functions.\n",
       "If an agent's explore function values curiositym N(s,a) will be low. Q learning can learn the optimal Q-function through off policy learningand not executing the optimal policy. \n",
       "Q learning will be come: \n",
       " $Q(s,a) = R(s,a,s')+γmax f(Q(s',a'),N(s',a'))$ \n",
       "\n",
       "\n",
       "Regret is a measure of your total mistake cost which includes the different between your expected rewards and optimal rewards. It quantifies the relative goodness of exploration procedures\n",
       "\n",
       "Basic Q learning keep a table of all q-values, which is too much to hold in memory. We can generalize it by learning small number of training states from experience and generalize that to new similar situations. \n",
       "\n",
       "Q(s,a)=w1f1(s,a)+w2f2(s,a)+...+wnfn(s,a) \n",
       "\n",
       "There might be cases that states with similar features but different values.\n",
       " \n",
       "\n",
       "## Module 9 Definitions\n",
       "* **Term** - your definition here\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "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))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "46MQLR-Gx8dZ"
   },
   "source": [
    "#Module 10 - Probabilities and Language Models"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 124,
   "metadata": {
    "id": "BN0b1eVYx-nd"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 12 “Quantifying Uncertainty” (Sections 12.1-12.7)\n",
    "equation13=r\"\"\"$\\mathbf{P}\\left(\\text { Cause, Effect }_{1}, \\ldots, \\text { Effect }_{n}\\right)=\\mathbf{P}(\\text { Cause }) \\prod_{i} \\mathbf{P}\\left(\\text { Effect }_{i} \\mid \\text { Cause }\\right)$\"\"\"\n",
    "equation14=r\"\"\"$P(b \\mid a)=\\frac{P(a \\mid b) P(b)}{P(a)}$\"\"\"\n",
    "equation15=r\"\"\"$\\mathbf{P}(Y \\mid X, \\mathbf{e})=\\frac{\\mathbf{P}(X \\mid Y, \\mathbf{e}) \\mathbf{P}(Y \\mid \\mathbf{e})}{\\mathbf{P}(X \\mid \\mathbf{e})}$\"\"\"\n",
    "equation16=r\"\"\"$\\mathbf{P}(\\mathbf{Y})=\\sum_{\\mathbf{z}} \\mathbf{P}(\\mathbf{Y}, \\mathbf{Z}=\\mathbf{z})$\"\"\"\n",
    "equation17=r\"\"\"$\\mathbf{P}(\\mathbf{Y})=\\sum_{\\mathbf{Z}} \\mathbf{P}(\\mathbf{Y} \\mid \\mathbf{Z}) P(\\mathbf{Z})$\"\"\"\n",
    "equation18=r\"\"\"$0 \\leq P(\\omega) \\leq 1 \\text { for every } \\omega \\text { and } \\sum_{\\omega \\in \\Omega} P(\\omega)=1$\"\"\"\n",
    "equation19=r\"\"\"$P(a \\mid b)=\\frac{P(a \\wedge b)}{P(b)}$\"\"\"\n",
    "equation20=r\"\"\"$P(a \\wedge b)=P(a \\mid b) P(b)$\"\"\"\n",
    "equation21=r\"\"\"$P(a \\mid b)=\\frac{P(a, b)}{P(b)}$\"\"\"\n",
    "equation22=r\"\"\"$P(y) P(x \\mid y)=P(x, y)$\"\"\"\n",
    "equation23=r\"\"\"$P\\left(x_{1}, x_{2}, x_{3}\\right)=P\\left(x_{1}\\right) P\\left(x_{2} \\mid x_{1}\\right) P\\left(x_{3} \\mid x_{1}, x_{2}\\right)$\"\"\"\n",
    "equation24=r\"\"\"$P\\left(x_{1}, x_{2}, \\ldots x_{n}\\right)=\\prod_{i} P\\left(x_{i} \\mid x_{1} \\ldots x_{i-1}\\right)$\"\"\"\n",
    "\n",
    "chapter12_1 = \"\"\" \n",
    "Logical agents handle uncertainty by keep track of belief state which includes all possible world state and have a plan for every event. This works for simple problems but has drawbacks\"\"\"+\"\\n\"+\"\"\"\n",
    "Agent must consider every possible event that its sensor observes, no matter how unlikely so it might keep a large belief-state with unlikely possibilities\"\"\"+\"\\n\"+\"\"\"\n",
    "A correct contingent that handles every event can grow large with arbitrarily unlikely contingencies \"\"\"+\"\\n\"+\"\"\"\n",
    "Sometime agent has to act when no plan is guaranteed to achieve goal yet. \"\"\"+\"\\n\"+\"\"\"\n",
    "Toothache example \"\"\"+\"\\n\"+\"\"\"\n",
    "1. Laziness: listing the complete set of antecedents requires an exceptionalness rule \n",
    "2. Theoretical ignorance: happens when there is no complete theory for the domain\n",
    "3. Practical ignorance: even if we know all rules we maybe not sure about a particular patient\n",
    "\n",
    "The agent can provide a degree of belief and we can use probability theory, which provides a way of summarizing uncertainty that comes from our laziness and ignorance\"\"\"+\"\\n\"+\"\"\"\n",
    "To make choices, an agent must have preferences among different possible outcomes of the various plans, which can be utility theory. The utility theory states that every state as a degree of usefulness and the agent will prefer states with higher utility. \"\"\"+\"\\n\"+\"\"\"\n",
    "Decision theory: Decision theory = probability theory + utility theory \"\"\"+\"\\n\"+\"\"\"\n",
    "Maximum expected utility: an agent is rational iff it chooses the action that yields the highest expected utility averaged over all possible outcomes \"\"\"+\"\\n\"+\"\"\"\n",
    "\n",
    " \"\"\"\n",
    "chapter12_2 = \"\"\" \n",
    "Probability assertions talk about how probable the various worlds are. All possible world sets is a sample space. Possible words are mutually exclusive and exhaustive \"\"\"+\"\\n\"+\"\"\"\n",
    "A fully specified probability model associates a numerical probability with each possible world. \"\"\"+\"\\n\"+\"\"\"\n",
    "The basic axion of probability theory states that every possible works has a P between 0 and 1, the total probability is :\"\"\"+\"\\n\"+equation18+\"\"\"\n",
    "\"\"\"+\"\\n\"+\"\"\"\n",
    "The probability associated with a proposition is defined to be the sum of probabilities of words in which it holds. For example: P(11)=P(5,6)+P(6,5) \"\"\"+\"\\n\"+\"\"\"\n",
    "For situations of prior probabilities: \"\"\"+\"\\n\"+equation19+\"\"\"\n",
    "\"\"\"+\"\\n\"+\"\"\"\n",
    "Product rule\"\"\"+\"\\n\"+equation20+\"\"\"\n",
    "\"\"\"+\"\\n\"+\"\"\"\n",
    "Variables in probability theory are random variables and begin with uppercase letter. Name for values are in lowercase. A boolean random variable has the range {true, false}. For discrete distribution we can have P(Weather) = ⟨0.6, 0.1, 0.29, 0.01⟩, for continuous distribution we can have P(NoonTemp = x) = Uniform(x; 18C, 26C), which is also called a probability density function. \"\"\"+\"\\n\"+\"\"\"\n",
    "A possible world is defined to be an assignment of values to all of the random variables under considerations\"\"\"+\"\\n\"+\"\"\"\n",
    "In addition to distribution on single variables, we also have notation for distributions on multiple variables using comma, for example, P(Weather, Cavity) denotes the probabilities of all combinations of values of Weather and Cavity. \"\"\"+\"\\n\"+\"\"\"\n",
    "P(Weather,Cavity) = P(Weather |Cavity)P(Cavity)\"\"\"+\"\\n\"+\"\"\"\n",
    "Full joint probability distribution: A probability model is completely determined  by the joint distribution for all of the random variables\"\"\"+\"\\n\"+\"\"\"\n",
    "Probability axion:\"\"\"+\"\\n\"+\"\"\"\n",
    "1. Negation: P(-a)=1-P(a)\n",
    "2. Inclusion-exclusion principle: P(a ∨ b) = P(a) + P(b) − P(a ∧ b)\n",
    " \"\"\"\n",
    "\n",
    "chapter12_3 = \"\"\" \n",
    "Marginalization/summing out: sum up the probabilities for each possible value of the other variables and taking them out of the equation \"\"\"+equation16+\"\"\"\n",
    "\"\"\"+\"\\n\"+\"\"\"\n",
    "Conditioning:\"\"\"+\"\\n\"+equation17\n",
    "chapter12_4 = \"\"\" \n",
    "If a and b are independent \"\"\"+\"\\n\"+\"\"\"\n",
    "\tP(a | b) = P(a) or P(b | a) = P(b) or P(a ∧ b) = P(a)P(b) \"\"\"+\"\\n\"+\"\"\"\n",
    "\tP(X| Y ) = P(X) or P(Y |X) = P(Y ) or P(X, Y ) = P(X)P(Y ). \"\"\"\n",
    "chapter12_5 = \"\"\" \n",
    "Basic Eequation: \"\"\"+equation14+\"\"\"\n",
    "\"\"\"+\"\\n\"+\"\"\"\n",
    "Adding an evidence e: \"\"\"+equation15+\"\"\"\n",
    "\"\"\"+\"\\n\"+\"\"\"\n",
    "General Bayes rule with normalization \"\"\"+\"\\n\"+\"\"\"\n",
    "\tP(Y|X) = αP(X|Y)P(Y) \"\"\"+\"\\n\"+\"\"\"\n",
    "\tα is the normalization constant that makes the entries in P(Y|X) sum to 1 \"\"\"+\"\\n\"+\"\"\"\n",
    "With a third variable Z, the conditional independence becomes \"\"\"+\"\\n\"+\"\"\"\n",
    "\tP(X, Y|Z) = P(X|Z)P(Y|Z). \"\"\"+\"\\n\"+\"\"\"\n",
    "\n",
    " \"\"\"\n",
    "\n",
    "chapter12_6 = \"\"\" A single cause can directly influences a number of effects that are conditionally independent. \n",
    "This is called a naive Bayes model because the effect variables are not strictly independent. \"\"\"+equation13+\"\"\" \"\"\"\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",
    "Axiom of probability: \"\"\"+\"\\n\"+\"\"\"\n",
    "1. The probability is always include 0 and 1 \n",
    "2. The probability of all possible worlds is 1 \n",
    "\n",
    "Marginal distributions are sub-tables with eliminate variables. \"\"\"+\"\\n\"+\"\"\"\n",
    "Conditional probabilities: \"\"\"+equation21+\"\"\"\n",
    "\"\"\"+\"\\n\"+\"\"\"\n",
    "Probabilistic inference is to compute a desired probability from other known probabilities \"\"\"+\"\\n\"+\"\"\"\n",
    "The product rule: \"\"\"+equation22+\"\"\"\n",
    "\"\"\"+\"\\n\"+\"\"\"\n",
    "The chain rule: \"\"\"+equation23+\"\"\" There are N! way to apply chain rule to a joint distribution with N variables\n",
    "\"\"\"+\"\\n\"+\"\"\"\n",
    "\"\"\"+equation24+\"\"\"\n",
    "\"\"\"+\"\\n\"+\"\"\"\n",
    "Baye's rule: P(x,y)=P(x|y)P(y)=P(y|x)P(x) \"\"\"+\"\\n\"+\"\"\"\n",
    "For example P(\"the underdog Philly\")=P(the) * P(underdog|the) * P(Philly|the underdog) \"\"\"+\"\\n\"+\"\"\"\n",
    "Markov assumption, or simple assumption, n-gram model simplfy this by only depends on the previous k words, not the whole context, \n",
    "or given the present state, future and past are independent. It makes it possible to estimate the probabilities from data. \n",
    "If it is a bigram model, then the probability of a word is determined only by a single preceding word.\n",
    "\"\"\"+\"\\n\"+\"\"\"\n",
    "The goal of Probablistic language model is to assign a probability to a sentence which can solve problems like autocompletion for texting, machine translation,\n",
    "spelling correction, and speech recognition, summerization, question-answering, dialog systems. \"\"\"+\"\\n\"+\"\"\"\n",
    "Related tasks include calculate the probability of an upcoming word\"\"\"+\"\\n\"+\"\"\" \n",
    "A language model (LM) calculate either of the above, P(W) or P(Wn|W1,W2,...Wn-1) \"\"\"+\"\\n\"+\"\"\"\n",
    "To construct a dynamic bayesian model, we need the sensor model, transition model, and prior distribution over the state variables.  \"\"\"+\"\\n\"+\"\"\"\n",
    "Ngram model is typically evaluated by perplexity on a test set.\n",
    "\n",
    " \"\"\"\n",
    "\n",
    "\n",
    "# Each definition should be at most 25 words long.\n",
    "module10_definitions = {\n",
    "\"term\" : \"your definition here\",\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 125,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 2172
    },
    "id": "lvtN3p7ET3Tx",
    "outputId": "f9781b74-6d96-4278-b6b0-597bec43aabc"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 10: Probabilies and Language Models\n",
       "## AIMA Chapter 12.1 Acting under Uncertainty\n",
       " \n",
       "Logical agents handle uncertainty by keep track of belief state which includes all possible world state and have a plan for every event. This works for simple problems but has drawbacks\n",
       "\n",
       "Agent must consider every possible event that its sensor observes, no matter how unlikely so it might keep a large belief-state with unlikely possibilities\n",
       "\n",
       "A correct contingent that handles every event can grow large with arbitrarily unlikely contingencies \n",
       "\n",
       "Sometime agent has to act when no plan is guaranteed to achieve goal yet. \n",
       "\n",
       "Toothache example \n",
       "\n",
       "1. Laziness: listing the complete set of antecedents requires an exceptionalness rule \n",
       "2. Theoretical ignorance: happens when there is no complete theory for the domain\n",
       "3. Practical ignorance: even if we know all rules we maybe not sure about a particular patient\n",
       "\n",
       "The agent can provide a degree of belief and we can use probability theory, which provides a way of summarizing uncertainty that comes from our laziness and ignorance\n",
       "\n",
       "To make choices, an agent must have preferences among different possible outcomes of the various plans, which can be utility theory. The utility theory states that every state as a degree of usefulness and the agent will prefer states with higher utility. \n",
       "\n",
       "Decision theory: Decision theory = probability theory + utility theory \n",
       "\n",
       "Maximum expected utility: an agent is rational iff it chooses the action that yields the highest expected utility averaged over all possible outcomes \n",
       "\n",
       "\n",
       " \n",
       "\n",
       "## AIMA Chapter 12.2 Basic Probability Notation\n",
       " \n",
       "Probability assertions talk about how probable the various worlds are. All possible world sets is a sample space. Possible words are mutually exclusive and exhaustive \n",
       "\n",
       "A fully specified probability model associates a numerical probability with each possible world. \n",
       "\n",
       "The basic axion of probability theory states that every possible works has a P between 0 and 1, the total probability is :\n",
       "$0 \\leq P(\\omega) \\leq 1 \\text { for every } \\omega \\text { and } \\sum_{\\omega \\in \\Omega} P(\\omega)=1$\n",
       "\n",
       "\n",
       "The probability associated with a proposition is defined to be the sum of probabilities of words in which it holds. For example: P(11)=P(5,6)+P(6,5) \n",
       "\n",
       "For situations of prior probabilities: \n",
       "$P(a \\mid b)=\\frac{P(a \\wedge b)}{P(b)}$\n",
       "\n",
       "\n",
       "Product rule\n",
       "$P(a \\wedge b)=P(a \\mid b) P(b)$\n",
       "\n",
       "\n",
       "Variables in probability theory are random variables and begin with uppercase letter. Name for values are in lowercase. A boolean random variable has the range {true, false}. For discrete distribution we can have P(Weather) = ⟨0.6, 0.1, 0.29, 0.01⟩, for continuous distribution we can have P(NoonTemp = x) = Uniform(x; 18C, 26C), which is also called a probability density function. \n",
       "\n",
       "A possible world is defined to be an assignment of values to all of the random variables under considerations\n",
       "\n",
       "In addition to distribution on single variables, we also have notation for distributions on multiple variables using comma, for example, P(Weather, Cavity) denotes the probabilities of all combinations of values of Weather and Cavity. \n",
       "\n",
       "P(Weather,Cavity) = P(Weather |Cavity)P(Cavity)\n",
       "\n",
       "Full joint probability distribution: A probability model is completely determined  by the joint distribution for all of the random variables\n",
       "\n",
       "Probability axion:\n",
       "\n",
       "1. Negation: P(-a)=1-P(a)\n",
       "2. Inclusion-exclusion principle: P(a ∨ b) = P(a) + P(b) − P(a ∧ b)\n",
       " \n",
       "\n",
       "## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n",
       " \n",
       "Marginalization/summing out: sum up the probabilities for each possible value of the other variables and taking them out of the equation $\\mathbf{P}(\\mathbf{Y})=\\sum_{\\mathbf{z}} \\mathbf{P}(\\mathbf{Y}, \\mathbf{Z}=\\mathbf{z})$\n",
       "\n",
       "\n",
       "Conditioning:\n",
       "$\\mathbf{P}(\\mathbf{Y})=\\sum_{\\mathbf{Z}} \\mathbf{P}(\\mathbf{Y} \\mid \\mathbf{Z}) P(\\mathbf{Z})$\n",
       "\n",
       "## AIMA Chapter 12.4 Independence\n",
       " \n",
       "If a and b are independent \n",
       "\n",
       "\tP(a | b) = P(a) or P(b | a) = P(b) or P(a ∧ b) = P(a)P(b) \n",
       "\n",
       "\tP(X| Y ) = P(X) or P(Y |X) = P(Y ) or P(X, Y ) = P(X)P(Y ). \n",
       "\n",
       "## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n",
       " \n",
       "Basic Eequation: $P(b \\mid a)=\\frac{P(a \\mid b) P(b)}{P(a)}$\n",
       "\n",
       "\n",
       "Adding an evidence e: $\\mathbf{P}(Y \\mid X, \\mathbf{e})=\\frac{\\mathbf{P}(X \\mid Y, \\mathbf{e}) \\mathbf{P}(Y \\mid \\mathbf{e})}{\\mathbf{P}(X \\mid \\mathbf{e})}$\n",
       "\n",
       "\n",
       "General Bayes rule with normalization \n",
       "\n",
       "\tP(Y|X) = αP(X|Y)P(Y) \n",
       "\n",
       "\tα is the normalization constant that makes the entries in P(Y|X) sum to 1 \n",
       "\n",
       "With a third variable Z, the conditional independence becomes \n",
       "\n",
       "\tP(X, Y|Z) = P(X|Z)P(Y|Z). \n",
       "\n",
       "\n",
       " \n",
       "\n",
       "## AIMA Chapter 12.6 Naive Bayes Models\n",
       " A single cause can directly influences a number of effects that are conditionally independent. \n",
       "This is called a naive Bayes model because the effect variables are not strictly independent. $\\mathbf{P}\\left(\\text { Cause, Effect }_{1}, \\ldots, \\text { Effect }_{n}\\right)=\\mathbf{P}(\\text { Cause }) \\prod_{i} \\mathbf{P}\\left(\\text { Effect }_{i} \\mid \\text { Cause }\\right)$ \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",
       "Axiom of probability: \n",
       "\n",
       "1. The probability is always include 0 and 1 \n",
       "2. The probability of all possible worlds is 1 \n",
       "\n",
       "Marginal distributions are sub-tables with eliminate variables. \n",
       "\n",
       "Conditional probabilities: $P(a \\mid b)=\\frac{P(a, b)}{P(b)}$\n",
       "\n",
       "\n",
       "Probabilistic inference is to compute a desired probability from other known probabilities \n",
       "\n",
       "The product rule: $P(y) P(x \\mid y)=P(x, y)$\n",
       "\n",
       "\n",
       "The chain rule: $P\\left(x_{1}, x_{2}, x_{3}\\right)=P\\left(x_{1}\\right) P\\left(x_{2} \\mid x_{1}\\right) P\\left(x_{3} \\mid x_{1}, x_{2}\\right)$ There are N! way to apply chain rule to a joint distribution with N variables\n",
       "\n",
       "\n",
       "$P\\left(x_{1}, x_{2}, \\ldots x_{n}\\right)=\\prod_{i} P\\left(x_{i} \\mid x_{1} \\ldots x_{i-1}\\right)$\n",
       "\n",
       "\n",
       "Baye's rule: P(x,y)=P(x|y)P(y)=P(y|x)P(x) \n",
       "\n",
       "For example P(\"the underdog Philly\")=P(the) * P(underdog|the) * P(Philly|the underdog) \n",
       "\n",
       "Markov assumption, or simple assumption, n-gram model simplfy this by only depends on the previous k words, not the whole context, \n",
       "or given the present state, future and past are independent. It makes it possible to estimate the probabilities from data. \n",
       "If it is a bigram model, then the probability of a word is determined only by a single preceding word.\n",
       "\n",
       "\n",
       "The goal of Probablistic language model is to assign a probability to a sentence which can solve problems like autocompletion for texting, machine translation,\n",
       "spelling correction, and speech recognition, summerization, question-answering, dialog systems. \n",
       "\n",
       "Related tasks include calculate the probability of an upcoming word\n",
       " \n",
       "A language model (LM) calculate either of the above, P(W) or P(Wn|W1,W2,...Wn-1) \n",
       "\n",
       "To construct a dynamic bayesian model, we need the sensor model, transition model, and prior distribution over the state variables.  \n",
       "\n",
       "Ngram model is typically evaluated by perplexity on a test set.\n",
       "\n",
       " \n",
       "\n",
       "## Module 10 Definitions\n",
       "* **Term** - your definition here\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "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))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "WHREsHSSyA-h"
   },
   "source": [
    "#Module 11 - Probabilistic Reasoning and Bayes’ Nets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 126,
   "metadata": {
    "id": "tuFC8w7CyCns"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
    "chapter13_1 = \"\"\" Your summary here \"\"\"\n",
    "chapter13_2 = \"\"\" Your summary here \"\"\"\n",
    "chapter13_3 = \"\"\" Your summary here \"\"\"\n",
    "equation25=r\"\"\"$\\forall x, y: P(x, y)=P(x) P(y)$\"\"\"\n",
    "equation26=r\"\"\"$\\forall x, y: P(x \\mid y)=P(x)$\"\"\"\n",
    "equation27=r\"\"\"$\\forall x, y, z: P(x, y \\mid z)=P(x \\mid z) P(y \\mid z)$\"\"\"\n",
    "equation28=r\"\"\"$\\forall x, y, z: P(x \\mid z, y)=P(x \\mid z)$\"\"\"\n",
    "equation29=r\"\"\"$P\\left(x_{1}, x_{2}, \\ldots x_{n}\\right)=\\prod_{i=1}^{n} P\\left(x_{i} \\mid \\text { parents }\\left(X_{i}\\right)\\right)$\"\"\"\n",
    "\n",
    "\n",
    "# Lecture notes \n",
    "module11_lecture_notes = \"\"\" \n",
    "Two variables are independent if \"\"\"+equation25+\"\"\"\n",
    "\"\"\"+\"\\n\"+\"\"\"\n",
    "or \"\"\"+equation26+\"\"\"\n",
    "\"\"\"+\"\\n\"+\"\"\"\n",
    "Conditional independence happens when \"\"\"+equation27+\"\"\"\n",
    "\"\"\"+\"\\n\"+\"\"\"\n",
    "or \"\"\"+equation28+\"\"\"\n",
    "\"\"\"+\"\\n\"+\"\"\"\n",
    "For example, P(detect|toothache,cavity)=P(detect|cavity) because detect is conditionally independent of toothache given cavity, toothache can be dropped\"\"\"+\"\\n\"+\"\"\"\n",
    "Apply to chain rule, becuase traffic is independent of umbrella given rain so it can be dropped \"\"\"+\"\\n\"+\"\"\"\n",
    "P(Traffic,Rain,Umbrella)=P(Rain)P(Traffic|Rain)P(Umbrella|Rain,Traffic)=P(Rain)P(Traffic|Rain)P(Umbrella|Rain) \"\"\"+\"\\n\"+\"\"\"\n",
    "Baye's net is a graphical technique for discribing complex joint distribution models using simple,local distribution. It solves the problem of full joint distribution table that is too big and hard to estimate mutiple variables at the same time. \"\"\"+\"\\n\"+\"\"\"\n",
    "Model is a directed, acyclic graph with a conditional distribution for each node. Or Bayes net=Topology(graph)+local conditional probability \"\"\"+\"\\n\"+\"\"\"\n",
    "Model notation: nodes are variables and arcs are interactions, arrow means conditional independence, not casual. \"\"\"+\"\\n\"+\"\"\"\n",
    "It implicitly encode joint distributions: \"\"\"+equation29+\"\"\"\n",
    "\"\"\"+\"\\n\"+\"\"\"\n",
    "The size of BN is O(N*2^(k+1)) with nodes have up to k parents, the size of joint distribution over N nodes is 2^N \"\"\"+\"\\n\"+\"\"\"\n",
    "\n",
    "D-separation gives precisioe conditional independence guarantee from graph alone, but it may have further independence that is not detectable until inspection: \"\"\"+\"\\n\"+\"\"\"\n",
    "1. X->Y->Z: X is not guaranteed independ of Z, but is conditionally independend of Z given Y, P(x,y,z)=P(x)P(y|x)P(z|y) \n",
    "2. Y->X and Y->Z, X is not guaranteed independ of Z, but is conditionally independend of Z given Y, P(x,y,z)=P(y)P(x|y)P(z|y) \n",
    "3. X->Z and Y->Z, X is independent of Y, but X and Y are not independent given Z \n",
    "\n",
    "To find reachability, we can shade the evidence node and look for path in the resulting graph: \"\"\"+\"\\n\"+\"\"\"\n",
    "1. if X and Y are conditionally independent then there is no active path \n",
    "2. A path is active if each triple is active. \n",
    "3. a single inactive segment can block a path \n",
    " \"\"\"\n",
    "\n",
    "# Definitions\n",
    "module11_definitions = {\n",
    "\"concept\" : \"definition\",    \n",
    "}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 127,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 816
    },
    "id": "vqtEs0gHs9sO",
    "outputId": "deae9c43-a6d5-4210-add6-7097f77c54fd"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n",
       "## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n",
       " Your summary here \n",
       "\n",
       "## AIMA 13.3 Exact Inference in Bayesian Networks\n",
       " Your summary here \n",
       "\n",
       "## Module 11 Lecture Notes\n",
       " \n",
       "Two variables are independent if $\\forall x, y: P(x, y)=P(x) P(y)$\n",
       "\n",
       "\n",
       "or $\\forall x, y: P(x \\mid y)=P(x)$\n",
       "\n",
       "\n",
       "Conditional independence happens when $\\forall x, y, z: P(x, y \\mid z)=P(x \\mid z) P(y \\mid z)$\n",
       "\n",
       "\n",
       "or $\\forall x, y, z: P(x \\mid z, y)=P(x \\mid z)$\n",
       "\n",
       "\n",
       "For example, P(detect|toothache,cavity)=P(detect|cavity) because detect is conditionally independent of toothache given cavity, toothache can be dropped\n",
       "\n",
       "Apply to chain rule, becuase traffic is independent of umbrella given rain so it can be dropped \n",
       "\n",
       "P(Traffic,Rain,Umbrella)=P(Rain)P(Traffic|Rain)P(Umbrella|Rain,Traffic)=P(Rain)P(Traffic|Rain)P(Umbrella|Rain) \n",
       "\n",
       "Baye's net is a graphical technique for discribing complex joint distribution models using simple,local distribution. It solves the problem of full joint distribution table that is too big and hard to estimate mutiple variables at the same time. \n",
       "\n",
       "Model is a directed, acyclic graph with a conditional distribution for each node. Or Bayes net=Topology(graph)+local conditional probability \n",
       "\n",
       "Model notation: nodes are variables and arcs are interactions, arrow means conditional independence, not casual. \n",
       "\n",
       "It implicitly encode joint distributions: $P\\left(x_{1}, x_{2}, \\ldots x_{n}\\right)=\\prod_{i=1}^{n} P\\left(x_{i} \\mid \\text { parents }\\left(X_{i}\\right)\\right)$\n",
       "\n",
       "\n",
       "The size of BN is O(N*2^(k+1)) with nodes have up to k parents, the size of joint distribution over N nodes is 2^N \n",
       "\n",
       "\n",
       "D-separation gives precisioe conditional independence guarantee from graph alone, but it may have further independence that is not detectable until inspection: \n",
       "\n",
       "1. X->Y->Z: X is not guaranteed independ of Z, but is conditionally independend of Z given Y, P(x,y,z)=P(x)P(y|x)P(z|y) \n",
       "2. Y->X and Y->Z, X is not guaranteed independ of Z, but is conditionally independend of Z given Y, P(x,y,z)=P(y)P(x|y)P(z|y) \n",
       "3. X->Z and Y->Z, X is independent of Y, but X and Y are not independent given Z \n",
       "\n",
       "To find reachability, we can shade the evidence node and look for path in the resulting graph: \n",
       "\n",
       "1. if X and Y are conditionally independent then there is no active path \n",
       "2. A path is active if each triple is active. \n",
       "3. a single inactive segment can block a path \n",
       " \n",
       "\n",
       "## Module 11 Definitions\n",
       "* **Concept** - definition\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "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))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "F3FPMzG9yUls"
   },
   "source": [
    "#Module 12 - Naive Bayes and Perceptrons"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 128,
   "metadata": {
    "id": "iEIOpL7vyWcc"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
    "\n",
    "chapter19_1 = \"\"\" A computer agent learning is called machine learning, which it observes data, build a model based on the data, and use the model to solve problems. \\n\n",
    "The improvent of agent program through machine depends on three factors, the first one is which component to be improved, the second one is what prior knowledge (that infuence the model) the agent has,\n",
    "and the data and feedback on the data. \\n\n",
    "There are three types of learnings with three types of feedbacks: \\n\n",
    "Supervised learning is when the agent a function that maps input to output through observations. Input can be pictures, output can be a label. \\n\n",
    "Unsupervised learning is when agent tries to learn patterns without explicit feedback, like clustering. The agent tries to detect clusters for inputs. \\n\n",
    "Reinforcement learning is when agent learns from a series of rewards and punishments. \n",
    "\"\"\"\n",
    "chapter19_2 = \"\"\" \n",
    "The goal for supervised learning is to find a function h, which is called a hythothesis about the world, that approximate the true mapping function f.\n",
    "H is drawn from a hypothesis space of possible functions. \\n\n",
    "Alternatively, h can represent a model of the data an H is a model class. \\n\n",
    "To choose a hythothesis space, we can based on prior knowledge or exploratory data analysis \\n\n",
    "Consistent hypothesis is when each xi in training set h(xi)=yi, whereas a best-fit match is each h(xi) close to yi. \\n\n",
    "To measure h, we need to exam how well it handles unseen input using a test set. h generalizes well if predicts output of test sets well \\n\n",
    "To analyze hypothesis space, we can look at bias and variance. Bias is regardless of the training set and measures the tendency of a predictive hypothesis to deviate\n",
    "from the expected value averaged over different traning sets. Bias is usually caused by hypothesis space restrictions. When hypothesis cannot find a pattern in data\n",
    "it is underfitting \\n \n",
    "Variance is the amount if change in the hypothesis caused by fluctuation in the training data. Sometimes when a function fit a particular data set too well it may overfit\n",
    "and cannot predict unseen data very well. \\n\n",
    "Bias-variance tradeoff happens when choosing between complex, low-bias hypotheses that fits the training data well and simpler and low-variance hypothese that generalize better. \n",
    "If a binary perceptron has a high bias values, it is easier for perceptron to output a 1.\n",
    " \"\"\"\n",
    "chapter19_3 = \"\"\" \n",
    "A decision tree makes decision through making tests from root through a leaf. Internal nodes represent a test, the branch represents possible values of the attribute,\n",
    "amd the leaf nodes represents the value to be returned. \\n\n",
    "Input and output can be discrete or continuous, a boolean input is discrete. It is the same as a logical statement: output=P1 V P2 V P3... \\n\n",
    "No representation is good for all kinds of functions. \\n\n",
    "Learn-Decision-Tree algorithm uses a greedy divide-and-conquer strategy which always tests the most important attribute first and recursively solve the smaller subproblems. In this way, the tree will be short and shallow. \\n\n",
    "To measure the importance of the attribute, we can use entropy, which measures the uncertainty of a random variable. In another word, the more information, the less entropy. \\n\n",
    "One way to solve overfitting is decision tree pruning which elimiates nodes that are not relevent. Irrelevence can be measured by information gain. \\n\n",
    "Another way is called early stopping which combines X^2 pruning and information gain, which stop the decision tree from generating new nodes when it has no good attribute to split on. \\n\n",
    "Decision tree is more useful when it can handle missing data, continuous and multivalued input attributes and continuous-valued output attribute.\n",
    " \"\"\"\n",
    "chapter19_4 = \"\"\" \n",
    "First we select stationarity assumption P(Ej) which makes future examples like the past. It has the same prior probability distribution and is independent of previous examples. \n",
    "Next we define optimal fit hypothesis which minimizes error rate. We estimate the error rate by measuring its performance on a test set. We usually divides data into training set which is used to train candidate models,\n",
    "validation set, also called development set or dev set, which is used to evaluate candidate models and choose the best one, and the test set which is used to conducting final evaluation and choose the best model. \n",
    "If we don't have enough data we can use k-fold cross validation. \\n\n",
    "There are two steps to find a good hypothesis, model selection and optimization or training. \\n\n",
    "For model selection, a learner takes a hyperparameter. It starts with the smallest size output a simple model and iterates to the larger sizes with complex models. \n",
    "Model selection will select the model which returns lowest average eeror on the held-out data. \\n \n",
    "Machine learning will choose to minimize loss function rather than maximize utility function. \\n\n",
    "Another approach to select model is regularization which penalize complex hypothesis. \\n\n",
    "When there are multiple hyperparameters, or with continuous value, we can use grid search which try all combinations of values, or random search when there are too many combinations for hyperparameter tuning.\n",
    "\"\"\"\n",
    "chapter19_5 = \"\"\" \n",
    "The computational learning theory states that very wrong hypothesis will be discovered after some examples, so hypothesis with large training sets should be Probably Approximately Correct. \\n\n",
    "To restrict the hypothesis without elimating the true function, we have three ways. The first way is to bring prior knowledge. The second way is to insist the algorithm returns a simple one. \n",
    "The third way focuses on learnable subsets and assumes that the restricted hypothesis spaces contains a h that is close to the true function f. \n",
    " \"\"\"\n",
    "chapter19_6 = \"\"\" \n",
    "Gradient descent is used to minimizing loss where we start with any point in the weight space, keep moving a small amount towards the steepest downhill direct until a local minimum. \n",
    "The step size is the learning rate. \n",
    " \"\"\"\n",
    "\n",
    "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
    "slp_chapter4_1 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter4_2 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter4_3 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter4_4 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter4_5 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter4_6 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter4_7 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter4_8 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter4_9 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter4_10 = \"\"\" Your summary here \"\"\"\n",
    "\n",
    "equation30=r\"\"\"$P\\left(Y, F_{1} \\ldots F_{n}\\right)=P(Y) \\prod_{i} P\\left(F_{i} \\mid Y\\right)$\"\"\"\n",
    "equation31=r\"\"\"$P_{L A P}(x)=\\frac{c(x)+1}{\\sum_{x}[c(x)+1]}$\"\"\"\n",
    "equation32=r\"\"\"$P_{L A P, k}(x)=\\frac{c(x)+k}{N+k|X|}$\"\"\"\n",
    "equation33=r\"\"\"$P_{L I N}(x \\mid y)=\\alpha \\widehat{P}(x \\mid y)+(1.0-\\alpha) \\widehat{P}(x)$\"\"\"\n",
    "equation34=r\"\"\"$\\operatorname{activation}_{w}(x)=\\sum_{i} w_{i} \\cdot f_{i}(x)=w \\cdot f(x)$\"\"\"\n",
    "equation35=r\"\"\"$y=\\left\\{\\begin{array}{ll}+1 & \\text { if } w \\cdot f(x) \\geq 0 \\n -1 & \\text { if } w \\cdot f(x)<0\\end{array}\\right.$\"\"\"\n",
    "equation36=r\"\"\"$w=w+y^{*} \\cdot f$\"\"\"\n",
    "equation37=r\"\"\"$w_{y}=w_{y}^{\\prime}-\\tau f(x)$\"\"\"\n",
    "equation38=r\"\"\"$\\tau^{*}=\\min \\left(\\frac{\\left(w_{y}^{\\prime}-w_{y^{*}}^{\\prime}\\right) \\cdot f+1}{2 f \\cdot f}, C\\right)$\"\"\"\n",
    "\n",
    "\n",
    "# Lecture notes \n",
    "module12_lecture_notes = \"\"\" \n",
    "Machine learning is the process to acquire a model from data and experience, like classification, spam/fraud detection. \\n\n",
    "For example, using Naive Bayes we can assume all features are independent effects of the label and try to learn \"\"\"+equation30+\"\"\"\n",
    "\\n\n",
    "Naive bayes has two utilizations, \\n\n",
    "The first is the inference method \\n\n",
    "1. get joint probability of label and evidence for each label \n",
    "2. sum to get probability of evidence \n",
    "3. normalize by dividing Step 1 by step 2 \n",
    "\n",
    "The second is to estimate local conditional probability tables \\n\n",
    "1. first calculate P(Y), the prior over labels \n",
    "2. calculate P(Fi|Y) for each feature \n",
    "\n",
    "To use NB for text, we follow below steps for bag-of-words, which the model is insensitive to word order: \\n\n",
    "1. The feattures Wi is the word at position i \n",
    "2. We want to predict label conditioned on feature variables \n",
    "3. We assume features are conditionally independent given label \n",
    "4. Each Wi is identically distributed \n",
    "\n",
    "For ML model, we have below features: \\n\n",
    "1. Data is separated into training set, held out set, and test set \n",
    "2. Features are attribute-value pairs which characterize each x \n",
    "3. Experiment cycle involves learning parameters on training set, tune hyperparameters on held-out data and compute accuracy on test sets \n",
    "4. Evaluation is to compute accuracy \n",
    "5. Prevent overfitting which fit the trainning data perfectly and improve generalization which needs to smooth or regularize the estimates\n",
    "  5.1 Normal estimate just use P=count(x)/total samples, but Laplace smoothing pretends to saw every outcome once more than actual \"\"\"+equation31+\"\"\"\n",
    "  5.2 or kth more than actual \"\"\"+equation32+\"\"\"\n",
    "  5.3 but Laplace perform poorly for P(X|Y) when X or Y is very large, so another option is linear interpolation \"\"\"+equation33+\"\"\"\n",
    "6. If there are errors, more features are needed to be added as new variables in NB model. \n",
    "\n",
    "Perceptrons are inspired by human neurons. \\n\n",
    "For linear classifiers inputs are feature values and each feature has a weight, the sum is the activation: \"\"\"+equation34+\"\"\"\n",
    "\\n\n",
    "For binary perceptron case: \\n\n",
    "1. start with weights =0 \n",
    "2. classify with current weights \"\"\"+equation35+\"\"\"\n",
    "3. If correct y=y* then no change, otherwise adjust the weight vector to  \"\"\"+equation36+\"\"\"\n",
    "\n",
    "For multi-class perceptron case: \\n\n",
    "1. Start a weight vector for each class wy \n",
    "2. calculate score of a class y w_y*f(x) \n",
    "3. prediction with highest score wins \n",
    "4. if correct then no change \n",
    "5. if wrong then lower score of wrong answer, raise score of right answer w_y=w_y-f(x), w_y*=w_y*+f(x) \n",
    "\n",
    "Perceptron are separabable if some parameters get the training set perfectly correct. If it is separable it will eventually converge in binary case. \\n\n",
    "Problems with perceptron includes when data is not separable weight will thrash. Overtraining may also lead to overfitting. \\n\n",
    "To solve these problems we can use MIRA which adjust the weight update to mitigate effect by choosing an update to fix the current mistake but minimize the change to w \"\"\"+equation37+\"\"\" and \"\"\"+equation38+\"\"\"\n",
    "Giving a cap C can prevent updates to be too large and make converge faster on noisy data \\n\n",
    "To decide which separation is better, a stategy is called SVM to maximize margin. \\n\n",
    "In conclution, NB build a model with training data and give prediction probabilities. It uses strong assumptions about feature independence and perform once pass over the data. Perceptron makes less assumptions about the data.\n",
    "It is also mistake-driven learning and use multiple passes over the data lead to more accurate results. \\n\n",
    "\\n\n",
    "If the separator are non linear, the origional feature space can be mapped to some higher-dimentional feature space whenre training set is separable. \\n\n",
    "Instead of using a linear activation function, we can also use a non-linear one, sigmoid(map output into range [0,1]), tanh(variant of sigmoid and maps outlier towards mean, or Rectified linear unit (ReLU) \\n\n",
    "Parametric models has a fized size on the number of parameters \n",
    "\"\"\"\n",
    "\n",
    "# Definitions\n",
    "module12_definitions = {\n",
    "\"induction\" : \"from sepecific observations to general rule, and the conclusion may be wrong\",    \n",
    "\"classification\":\"output is one of a set of values\",\n",
    "\"regression\":\"output is a number\",\n",
    "\"training set\":\"a list of input-output pairs\",\n",
    "\"EDA\":\"examing data with statistical tests and visualizations\",\n",
    "\"decision tree\":\"a function that maps attributes to a single decision output\",\n",
    "\"univariate linear function\": \"straight line function\",\n",
    "\"linear regression\":\"find hw=w1x+w0\",\n",
    "\"weight space\":\"all possible values of the weights\",\n",
    "\"epoch\":\"a step that have all training data\"\n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 129,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 3393
    },
    "id": "KUc_LgzDvWf-",
    "outputId": "feb8da4d-3a06-41e6-c452-5288fd57d74b"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 12: Naive Bayes and Perceptrons\n",
       "## AIMA Chapter 19.1 Forms of Learning\n",
       " A computer agent learning is called machine learning, which it observes data, build a model based on the data, and use the model to solve problems. \n",
       "\n",
       "The improvent of agent program through machine depends on three factors, the first one is which component to be improved, the second one is what prior knowledge (that infuence the model) the agent has,\n",
       "and the data and feedback on the data. \n",
       "\n",
       "There are three types of learnings with three types of feedbacks: \n",
       "\n",
       "Supervised learning is when the agent a function that maps input to output through observations. Input can be pictures, output can be a label. \n",
       "\n",
       "Unsupervised learning is when agent tries to learn patterns without explicit feedback, like clustering. The agent tries to detect clusters for inputs. \n",
       "\n",
       "Reinforcement learning is when agent learns from a series of rewards and punishments. \n",
       "\n",
       "\n",
       "## AIMA Chapter 19.2 Supervised Learning\n",
       " \n",
       "The goal for supervised learning is to find a function h, which is called a hythothesis about the world, that approximate the true mapping function f.\n",
       "H is drawn from a hypothesis space of possible functions. \n",
       "\n",
       "Alternatively, h can represent a model of the data an H is a model class. \n",
       "\n",
       "To choose a hythothesis space, we can based on prior knowledge or exploratory data analysis \n",
       "\n",
       "Consistent hypothesis is when each xi in training set h(xi)=yi, whereas a best-fit match is each h(xi) close to yi. \n",
       "\n",
       "To measure h, we need to exam how well it handles unseen input using a test set. h generalizes well if predicts output of test sets well \n",
       "\n",
       "To analyze hypothesis space, we can look at bias and variance. Bias is regardless of the training set and measures the tendency of a predictive hypothesis to deviate\n",
       "from the expected value averaged over different traning sets. Bias is usually caused by hypothesis space restrictions. When hypothesis cannot find a pattern in data\n",
       "it is underfitting \n",
       " \n",
       "Variance is the amount if change in the hypothesis caused by fluctuation in the training data. Sometimes when a function fit a particular data set too well it may overfit\n",
       "and cannot predict unseen data very well. \n",
       "\n",
       "Bias-variance tradeoff happens when choosing between complex, low-bias hypotheses that fits the training data well and simpler and low-variance hypothese that generalize better. \n",
       "If a binary perceptron has a high bias values, it is easier for perceptron to output a 1.\n",
       " \n",
       "\n",
       "## AIMA Chapter 19.3 Learning Decision Trees\n",
       " \n",
       "A decision tree makes decision through making tests from root through a leaf. Internal nodes represent a test, the branch represents possible values of the attribute,\n",
       "amd the leaf nodes represents the value to be returned. \n",
       "\n",
       "Input and output can be discrete or continuous, a boolean input is discrete. It is the same as a logical statement: output=P1 V P2 V P3... \n",
       "\n",
       "No representation is good for all kinds of functions. \n",
       "\n",
       "Learn-Decision-Tree algorithm uses a greedy divide-and-conquer strategy which always tests the most important attribute first and recursively solve the smaller subproblems. In this way, the tree will be short and shallow. \n",
       "\n",
       "To measure the importance of the attribute, we can use entropy, which measures the uncertainty of a random variable. In another word, the more information, the less entropy. \n",
       "\n",
       "One way to solve overfitting is decision tree pruning which elimiates nodes that are not relevent. Irrelevence can be measured by information gain. \n",
       "\n",
       "Another way is called early stopping which combines X^2 pruning and information gain, which stop the decision tree from generating new nodes when it has no good attribute to split on. \n",
       "\n",
       "Decision tree is more useful when it can handle missing data, continuous and multivalued input attributes and continuous-valued output attribute.\n",
       " \n",
       "\n",
       "## AIMA Chapter 19.4 Model Selection and Optimization\n",
       " \n",
       "First we select stationarity assumption P(Ej) which makes future examples like the past. It has the same prior probability distribution and is independent of previous examples. \n",
       "Next we define optimal fit hypothesis which minimizes error rate. We estimate the error rate by measuring its performance on a test set. We usually divides data into training set which is used to train candidate models,\n",
       "validation set, also called development set or dev set, which is used to evaluate candidate models and choose the best one, and the test set which is used to conducting final evaluation and choose the best model. \n",
       "If we don't have enough data we can use k-fold cross validation. \n",
       "\n",
       "There are two steps to find a good hypothesis, model selection and optimization or training. \n",
       "\n",
       "For model selection, a learner takes a hyperparameter. It starts with the smallest size output a simple model and iterates to the larger sizes with complex models. \n",
       "Model selection will select the model which returns lowest average eeror on the held-out data. \n",
       " \n",
       "Machine learning will choose to minimize loss function rather than maximize utility function. \n",
       "\n",
       "Another approach to select model is regularization which penalize complex hypothesis. \n",
       "\n",
       "When there are multiple hyperparameters, or with continuous value, we can use grid search which try all combinations of values, or random search when there are too many combinations for hyperparameter tuning.\n",
       "\n",
       "\n",
       "## AIMA Chapter 19.5 The Theory of Learning\n",
       " \n",
       "The computational learning theory states that very wrong hypothesis will be discovered after some examples, so hypothesis with large training sets should be Probably Approximately Correct. \n",
       "\n",
       "To restrict the hypothesis without elimating the true function, we have three ways. The first way is to bring prior knowledge. The second way is to insist the algorithm returns a simple one. \n",
       "The third way focuses on learnable subsets and assumes that the restricted hypothesis spaces contains a h that is close to the true function f. \n",
       " \n",
       "\n",
       "## AIMA Chapter 19.6 Linear Regression and Classification\n",
       " \n",
       "Gradient descent is used to minimizing loss where we start with any point in the weight space, keep moving a small amount towards the steepest downhill direct until a local minimum. \n",
       "The step size is the learning rate. \n",
       " \n",
       "\n",
       "## SLP Chapter 4.1 Naive Bayes Classifiers\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.2 Training the Naive Bayes Classifier\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.3 Worked Example\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.6 Naive Bayes as a Language Model\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.8 Test sets and Cross-validation\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.9 Statistical Significance Testing\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.10 Avoiding Harms in Classification\n",
       " Your summary here \n",
       "\n",
       "## Module 12 Lecture Notes\n",
       " \n",
       "Machine learning is the process to acquire a model from data and experience, like classification, spam/fraud detection. \n",
       "\n",
       "For example, using Naive Bayes we can assume all features are independent effects of the label and try to learn $P\\left(Y, F_{1} \\ldots F_{n}\\right)=P(Y) \\prod_{i} P\\left(F_{i} \\mid Y\\right)$\n",
       "\n",
       "\n",
       "Naive bayes has two utilizations, \n",
       "\n",
       "The first is the inference method \n",
       "\n",
       "1. get joint probability of label and evidence for each label \n",
       "2. sum to get probability of evidence \n",
       "3. normalize by dividing Step 1 by step 2 \n",
       "\n",
       "The second is to estimate local conditional probability tables \n",
       "\n",
       "1. first calculate P(Y), the prior over labels \n",
       "2. calculate P(Fi|Y) for each feature \n",
       "\n",
       "To use NB for text, we follow below steps for bag-of-words, which the model is insensitive to word order: \n",
       "\n",
       "1. The feattures Wi is the word at position i \n",
       "2. We want to predict label conditioned on feature variables \n",
       "3. We assume features are conditionally independent given label \n",
       "4. Each Wi is identically distributed \n",
       "\n",
       "For ML model, we have below features: \n",
       "\n",
       "1. Data is separated into training set, held out set, and test set \n",
       "2. Features are attribute-value pairs which characterize each x \n",
       "3. Experiment cycle involves learning parameters on training set, tune hyperparameters on held-out data and compute accuracy on test sets \n",
       "4. Evaluation is to compute accuracy \n",
       "5. Prevent overfitting which fit the trainning data perfectly and improve generalization which needs to smooth or regularize the estimates\n",
       "  5.1 Normal estimate just use P=count(x)/total samples, but Laplace smoothing pretends to saw every outcome once more than actual $P_{L A P}(x)=\\frac{c(x)+1}{\\sum_{x}[c(x)+1]}$\n",
       "  5.2 or kth more than actual $P_{L A P, k}(x)=\\frac{c(x)+k}{N+k|X|}$\n",
       "  5.3 but Laplace perform poorly for P(X|Y) when X or Y is very large, so another option is linear interpolation $P_{L I N}(x \\mid y)=\\alpha \\widehat{P}(x \\mid y)+(1.0-\\alpha) \\widehat{P}(x)$\n",
       "6. If there are errors, more features are needed to be added as new variables in NB model. \n",
       "\n",
       "Perceptrons are inspired by human neurons. \n",
       "\n",
       "For linear classifiers inputs are feature values and each feature has a weight, the sum is the activation: $\\operatorname{activation}_{w}(x)=\\sum_{i} w_{i} \\cdot f_{i}(x)=w \\cdot f(x)$\n",
       "\n",
       "\n",
       "For binary perceptron case: \n",
       "\n",
       "1. start with weights =0 \n",
       "2. classify with current weights $y=\\left\\{\\begin{array}{ll}+1 & \\text { if } w \\cdot f(x) \\geq 0 \\n -1 & \\text { if } w \\cdot f(x)<0\\end{array}\\right.$\n",
       "3. If correct y=y* then no change, otherwise adjust the weight vector to  $w=w+y^{*} \\cdot f$\n",
       "\n",
       "For multi-class perceptron case: \n",
       "\n",
       "1. Start a weight vector for each class wy \n",
       "2. calculate score of a class y w_y*f(x) \n",
       "3. prediction with highest score wins \n",
       "4. if correct then no change \n",
       "5. if wrong then lower score of wrong answer, raise score of right answer w_y=w_y-f(x), w_y*=w_y*+f(x) \n",
       "\n",
       "Perceptron are separabable if some parameters get the training set perfectly correct. If it is separable it will eventually converge in binary case. \n",
       "\n",
       "Problems with perceptron includes when data is not separable weight will thrash. Overtraining may also lead to overfitting. \n",
       "\n",
       "To solve these problems we can use MIRA which adjust the weight update to mitigate effect by choosing an update to fix the current mistake but minimize the change to w $w_{y}=w_{y}^{\\prime}-\\tau f(x)$ and $\\tau^{*}=\\min \\left(\\frac{\\left(w_{y}^{\\prime}-w_{y^{*}}^{\\prime}\\right) \\cdot f+1}{2 f \\cdot f}, C\\right)$\n",
       "Giving a cap C can prevent updates to be too large and make converge faster on noisy data \n",
       "\n",
       "To decide which separation is better, a stategy is called SVM to maximize margin. \n",
       "\n",
       "In conclution, NB build a model with training data and give prediction probabilities. It uses strong assumptions about feature independence and perform once pass over the data. Perceptron makes less assumptions about the data.\n",
       "It is also mistake-driven learning and use multiple passes over the data lead to more accurate results. \n",
       "\n",
       "\n",
       "\n",
       "If the separator are non linear, the origional feature space can be mapped to some higher-dimentional feature space whenre training set is separable. \n",
       "\n",
       "Instead of using a linear activation function, we can also use a non-linear one, sigmoid(map output into range [0,1]), tanh(variant of sigmoid and maps outlier towards mean, or Rectified linear unit (ReLU) \n",
       "\n",
       "Parametric models has a fized size on the number of parameters \n",
       "\n",
       "\n",
       "## Module 12 Definitions\n",
       "* **Induction** - from sepecific observations to general rule, and the conclusion may be wrong\n",
       "* **Classification** - output is one of a set of values\n",
       "* **Regression** - output is a number\n",
       "* **Training set** - a list of input-output pairs\n",
       "* **Eda** - examing data with statistical tests and visualizations\n",
       "* **Decision tree** - a function that maps attributes to a single decision output\n",
       "* **Univariate linear function** - straight line function\n",
       "* **Linear regression** - find hw=w1x+w0\n",
       "* **Weight space** - all possible values of the weights\n",
       "* **Epoch** - a step that have all training data\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#@title Preview of your summary\n",
    "#@markdown You don't need to modify anything in this cell. Just press play.\n",
    "module12_sections = [\n",
    "  (\"AIMA Chapter 19.1 Forms of Learning\", chapter19_1),\n",
    "  (\"AIMA Chapter 19.2 Supervised Learning\", chapter19_2),\n",
    "  (\"AIMA Chapter 19.3 Learning Decision Trees\", chapter19_3),\n",
    "  (\"AIMA Chapter 19.4 Model Selection and Optimization\", chapter19_4),\n",
    "  (\"AIMA Chapter 19.5 The Theory of Learning\", chapter19_5),\n",
    "  (\"AIMA Chapter 19.6 Linear Regression and Classification\", chapter19_6),\n",
    "  (\"SLP Chapter 4.1 Naive Bayes Classifiers\", slp_chapter4_1),\n",
    "  (\"SLP Chapter 4.2 Training the Naive Bayes Classifier\", slp_chapter4_2),\n",
    "  (\"SLP Chapter 4.3 Worked Example\", slp_chapter4_3),\n",
    "  (\"SLP Chapter 4.4 Optimizing for Sentiment Analysis\", slp_chapter4_4),\n",
    "  (\"SLP Chapter 4.5 Naive Bayes for other text classification tasks\", slp_chapter4_5),\n",
    "  (\"SLP Chapter 4.6 Naive Bayes as a Language Model\", slp_chapter4_6),\n",
    "  (\"SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\", slp_chapter4_7),\n",
    "  (\"SLP Chapter 4.8 Test sets and Cross-validation\", slp_chapter4_8),\n",
    "  (\"SLP Chapter 4.9 Statistical Significance Testing\", slp_chapter4_9),\n",
    "  (\"SLP Chapter 4.10 Avoiding Harms in Classification\", slp_chapter4_10),\n",
    "  (\"Module 12 Lecture Notes\", module12_lecture_notes),\n",
    "]\n",
    "\n",
    "module12_markdown = format_module(12, \"Naive Bayes and Perceptrons\", \n",
    "                         module12_sections, \n",
    "                         module12_definitions)\n",
    "display(Markdown(module12_markdown))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "qVSQhTVSyYYO"
   },
   "source": [
    "# Module 13 - Neural Networks"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 130,
   "metadata": {
    "id": "Wm4mfW82yaRH"
   },
   "outputs": [],
   "source": [
    "# Jurafsky and Martin, Speech and Language Processing Chapter 5 “Logistic Regression” (5.1-5.6)\n",
    "\n",
    "slp_chapter5_1 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter5_2 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter5_3 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter5_4 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter5_5 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter5_6 = \"\"\" Your summary here \"\"\"\n",
    "\n",
    "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
    "\n",
    "slp_chapter7_1 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter7_2 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter7_3 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter7_4 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter7_5 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter7_6 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter7_7 = \"\"\" Your summary here \"\"\"\n",
    "\n",
    "equation39=r\"\"\"$P(y=1)=\\sigma(w \\cdot x+b)=\\frac{1}{1+e^{-(w \\cdot x+b)}}$\"\"\"\n",
    "equation40=r\"\"\"$\\hat{y}=\\left\\{\\begin{array}{c}\n",
    "1 \\text { if } P(y=1 \\mid x)>0.5 \\\\\n",
    "0 \\text { otherwise }\n",
    "\\end{array}\\right.$\"\"\"\n",
    "equation41=r\"\"\"$L_{M S E}(\\hat{y}, y)=\\frac{1}{2}(\\hat{y}-y)^{2}$\"\"\"\n",
    "equation42=r\"\"\"$L_{C E}(\\hat{y}, y)=-[y \\log \\sigma(w \\cdot x+b)+(1-y) \\log (1-\\sigma(w \\cdot x+b))]$\"\"\"\n",
    "equation43=r\"\"\"$\\operatorname{Cost}(w, b)=-\\frac{1}{m} \\sum_{i=1}^{m} y^{(i)} \\log \\sigma\\left(w \\cdot x^{(i)}+b\\right)+\\left(1-y^{(i)}\\right) \\log \\left(1-\\sigma\\left(w \\cdot x^{(i)}+b\\right)\\right)$\"\"\"\n",
    "equation44=r\"\"\"$\\frac{\\partial \\operatorname{Cost}(w, b)}{\\partial w_{j}}=\\sum_{i=1}^{m}\\left[\\sigma\\left(w \\cdot x^{(i)}+b\\right)-y^{(i)}\\right] x_{j}^{(i)}$\"\"\"\n",
    "equation45=r\"\"\"$\\operatorname{softmax}\\left(z_{i}\\right)=\\frac{e^{z_{j}}}{\\sum_{j=1}^{k} e^{z_{j}}} 1 \\leq i \\leq k$\"\"\"\n",
    "equation46=r\"\"\"$\\sigma(z)=\\frac{1}{1+e^{-z}}$\"\"\"\n",
    "equation47=r\"\"\"$\\frac{d f}{d x}=\\frac{d u}{d v} \\cdot \\frac{d v}{d w} \\cdot \\frac{d w}{d x}$\"\"\"\n",
    "\n",
    "# Lecture notes \n",
    "module13_lecture_notes = \"\"\" \n",
    "Classifier has following components: \\n\n",
    "1. A feature representation of the input, for each input xi there is a vector of features [x1,x2,...xn] \n",
    "2. A classification function that computes estimated y \n",
    "3. An objective function for learning that involves minimizing errors \n",
    "4. An algorithm for optimizing the objective function. \n",
    "\n",
    "For example, for sentiment classifier we can use a logistic regression which learns a vector of weights and a bia term z=w*x+b \"\"\"+equation39+\"\"\"\n",
    "\\n\n",
    "And we can make a decision using a arbitarty dicision boundry, 0.5 in this case \"\"\"+equation40+\"\"\"\n",
    "\\n\n",
    "To learn the weights and bias, we need 2 components: \\n\n",
    "1. An objective function or loss function that tells us the distance between the system output and the gold output \n",
    "2. An algorithm like stochastic gradient descent to optimize the objective function and minimize the loss function, which is how much estimated y different from true y \n",
    "\n",
    "We can use mean squared error for example \"\"\"+equation41+\"\"\"\n",
    "\\n\n",
    "We can also use cross-entropy loss which is negative log likelihood loss\"\"\"+equation42+\"\"\"\n",
    "\\n\n",
    "\\n\n",
    "Gradient descent is a method to find a minimum of a function by figuring out in which direction the function's slope is rising the most deeply and moving in the opposite direction.\\n\n",
    "Logistic regress's loss function is convex with just 1 minumim, so there is no local minimum. \\n\n",
    "The magnitude of amount to move in gradient descent is called larning rate. Faster learning has higher learning rate. \\n\n",
    "The loss for a batch of data or entire dataset is the average loss over m examples\"\"\"+equation43+\"\"\"\n",
    "\\n\n",
    "The gradient for multiple data point is the sum of individual gradients\"\"\"+equation44+\"\"\"\n",
    "\\n\n",
    "Stochastic GD chooses a single random example at a time and updates its weight on that example, but the update can fluctuate. \n",
    "An alternative is batch training which computes the gradient over the entire dataset. This method gives better estimate on which direct to move but takes long time to compute. \n",
    "So a commonly used compromise is mini-batch training.\\n\n",
    "\\n\n",
    "Overfitting will result poor generalization and performance on unseen test. In logistic regression, a feature only occur in one class will get a high weight, \n",
    "so we need to add regularization to loss function penalize large weights. L1 is Lasso and L2 is ridge. \\n\n",
    "\\n\n",
    "Apart from binary classifition we may want to classify into more than two classes, and we want to know the probability of each class. \n",
    "We will use a generalization of the sigmoid function called softmax to get proper probability which takes input of vector z and outputs a vector of values normalized into probabilities \"\"\"+equation45+\"\"\"\n",
    "\\n\n",
    "Instead of outputtomg z directly, logistic regression transforms it with sigmoid function which solve the problem that a small change in weights or bias can cause output to completely flip from 0 to 1\"\"\"+equation46+\"\"\"\n",
    " where z=w·x+b \\n\n",
    " This smoothness makes it easy to choose small change in weights and biases to achieve small change in the output. \\n\n",
    " \\n\n",
    "The simplest kind of NN is the feed forward NN which is a multilayer network that all units are fully connected with no cycles.\n",
    "Outputs from each layer are passed to the next layer and no output are passed back to lower layers. \\n\n",
    "We represents parameter for the entire hidden layer by combining the wi and bi for each unit i into a single weight matrix W and a single bias vector b for the whole layer.\\n\n",
    "Advantage of using a single matrix is that the hidden layer computation can be done with matrix operations \\n\n",
    "1. multiply the weight matri by input vector x \n",
    "2. adding the bias vector b \n",
    "3. apply activation g: h = σ(Wx+b) \n",
    "\n",
    "Like the hidden layer, the output layer also has a weight matrix U. Its weight matrix is multiplied by input vector h to produce intermediate output z: z=Uh. \\n\n",
    "\\n\n",
    "The final equations for a feedforward network with a single hidden layer, which takes an input vector x, outputs a probability distribution y, and is parameterized by weights matrices W and U and a bias vector b: \\n\n",
    "h = σ(Wx+b)\\n\n",
    "z=Uh\\n\n",
    "y=softmax(z)\\n\n",
    "\\n\n",
    "NN stacks layers relative to perceptrons. \\n\n",
    "If we use liner activation function, the resulting nn will be a single layer nn \\n\n",
    "To train neural nets, we need to learn the best paraments, so we need a loss function (cross-entropy loss), \n",
    "an optimization algorithm (gradient descent), and a way of computing the gradient of the loss function (error propagation). \\n\n",
    "Backpropagation is invented for nn, but is related to general procedure called backward differentiation, which uses chain rule. \n",
    "It computes the gradient of loss function which requires looking back through all layers in the networkenables us to correctly update all layers in nn \\n\n",
    "For f(x) = u(v(w(x))), the derivative of f(x) is \"\"\"+equation47\n",
    "\n",
    "# Definitions\n",
    "module13_definitions = {\n",
    "\"concept\" : \"definition\",    \n",
    "}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 131,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 2140
    },
    "id": "kKWbCsbfxL3R",
    "outputId": "71c8ef76-d446-42e1-dbb2-481103bc4c58"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 13: Neural Networks\n",
       "## SLP Chapter 5.1 Classification: the sigmoid\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 5.2 Learning in Logistic Regression\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 5.3 The cross-entropy loss function\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 5.4 Gradient Descent\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 5.5 Regularization\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 5.6 Multinomial logistic regression\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.1 Units\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.2 The XOR problem\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.3 Feedforward Neural Networks\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.5 Feedforward Neural Language Modeling\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.6 Training Neural Nets\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.7 Training the neural language model\n",
       " Your summary here \n",
       "\n",
       "## Module 13 Lecture Notes\n",
       " \n",
       "Classifier has following components: \n",
       "\n",
       "1. A feature representation of the input, for each input xi there is a vector of features [x1,x2,...xn] \n",
       "2. A classification function that computes estimated y \n",
       "3. An objective function for learning that involves minimizing errors \n",
       "4. An algorithm for optimizing the objective function. \n",
       "\n",
       "For example, for sentiment classifier we can use a logistic regression which learns a vector of weights and a bia term z=w*x+b $P(y=1)=\\sigma(w \\cdot x+b)=\\frac{1}{1+e^{-(w \\cdot x+b)}}$\n",
       "\n",
       "\n",
       "And we can make a decision using a arbitarty dicision boundry, 0.5 in this case $\\hat{y}=\\left\\{\\begin{array}{c}\n",
       "1 \\text { if } P(y=1 \\mid x)>0.5 \\\\\n",
       "0 \\text { otherwise }\n",
       "\\end{array}\\right.$\n",
       "\n",
       "\n",
       "To learn the weights and bias, we need 2 components: \n",
       "\n",
       "1. An objective function or loss function that tells us the distance between the system output and the gold output \n",
       "2. An algorithm like stochastic gradient descent to optimize the objective function and minimize the loss function, which is how much estimated y different from true y \n",
       "\n",
       "We can use mean squared error for example $L_{M S E}(\\hat{y}, y)=\\frac{1}{2}(\\hat{y}-y)^{2}$\n",
       "\n",
       "\n",
       "We can also use cross-entropy loss which is negative log likelihood loss$L_{C E}(\\hat{y}, y)=-[y \\log \\sigma(w \\cdot x+b)+(1-y) \\log (1-\\sigma(w \\cdot x+b))]$\n",
       "\n",
       "\n",
       "\n",
       "\n",
       "Gradient descent is a method to find a minimum of a function by figuring out in which direction the function's slope is rising the most deeply and moving in the opposite direction.\n",
       "\n",
       "Logistic regress's loss function is convex with just 1 minumim, so there is no local minimum. \n",
       "\n",
       "The magnitude of amount to move in gradient descent is called larning rate. Faster learning has higher learning rate. \n",
       "\n",
       "The loss for a batch of data or entire dataset is the average loss over m examples$\\operatorname{Cost}(w, b)=-\\frac{1}{m} \\sum_{i=1}^{m} y^{(i)} \\log \\sigma\\left(w \\cdot x^{(i)}+b\\right)+\\left(1-y^{(i)}\\right) \\log \\left(1-\\sigma\\left(w \\cdot x^{(i)}+b\\right)\\right)$\n",
       "\n",
       "\n",
       "The gradient for multiple data point is the sum of individual gradients$\\frac{\\partial \\operatorname{Cost}(w, b)}{\\partial w_{j}}=\\sum_{i=1}^{m}\\left[\\sigma\\left(w \\cdot x^{(i)}+b\\right)-y^{(i)}\\right] x_{j}^{(i)}$\n",
       "\n",
       "\n",
       "Stochastic GD chooses a single random example at a time and updates its weight on that example, but the update can fluctuate. \n",
       "An alternative is batch training which computes the gradient over the entire dataset. This method gives better estimate on which direct to move but takes long time to compute. \n",
       "So a commonly used compromise is mini-batch training.\n",
       "\n",
       "\n",
       "\n",
       "Overfitting will result poor generalization and performance on unseen test. In logistic regression, a feature only occur in one class will get a high weight, \n",
       "so we need to add regularization to loss function penalize large weights. L1 is Lasso and L2 is ridge. \n",
       "\n",
       "\n",
       "\n",
       "Apart from binary classifition we may want to classify into more than two classes, and we want to know the probability of each class. \n",
       "We will use a generalization of the sigmoid function called softmax to get proper probability which takes input of vector z and outputs a vector of values normalized into probabilities $\\operatorname{softmax}\\left(z_{i}\\right)=\\frac{e^{z_{j}}}{\\sum_{j=1}^{k} e^{z_{j}}} 1 \\leq i \\leq k$\n",
       "\n",
       "\n",
       "Instead of outputtomg z directly, logistic regression transforms it with sigmoid function which solve the problem that a small change in weights or bias can cause output to completely flip from 0 to 1$\\sigma(z)=\\frac{1}{1+e^{-z}}$\n",
       " where z=w·x+b \n",
       "\n",
       " This smoothness makes it easy to choose small change in weights and biases to achieve small change in the output. \n",
       "\n",
       " \n",
       "\n",
       "The simplest kind of NN is the feed forward NN which is a multilayer network that all units are fully connected with no cycles.\n",
       "Outputs from each layer are passed to the next layer and no output are passed back to lower layers. \n",
       "\n",
       "We represents parameter for the entire hidden layer by combining the wi and bi for each unit i into a single weight matrix W and a single bias vector b for the whole layer.\n",
       "\n",
       "Advantage of using a single matrix is that the hidden layer computation can be done with matrix operations \n",
       "\n",
       "1. multiply the weight matri by input vector x \n",
       "2. adding the bias vector b \n",
       "3. apply activation g: h = σ(Wx+b) \n",
       "\n",
       "Like the hidden layer, the output layer also has a weight matrix U. Its weight matrix is multiplied by input vector h to produce intermediate output z: z=Uh. \n",
       "\n",
       "\n",
       "\n",
       "The final equations for a feedforward network with a single hidden layer, which takes an input vector x, outputs a probability distribution y, and is parameterized by weights matrices W and U and a bias vector b: \n",
       "\n",
       "h = σ(Wx+b)\n",
       "\n",
       "z=Uh\n",
       "\n",
       "y=softmax(z)\n",
       "\n",
       "\n",
       "\n",
       "NN stacks layers relative to perceptrons. \n",
       "\n",
       "If we use liner activation function, the resulting nn will be a single layer nn \n",
       "\n",
       "To train neural nets, we need to learn the best paraments, so we need a loss function (cross-entropy loss), \n",
       "an optimization algorithm (gradient descent), and a way of computing the gradient of the loss function (error propagation). \n",
       "\n",
       "Backpropagation is invented for nn, but is related to general procedure called backward differentiation, which uses chain rule. \n",
       "It computes the gradient of loss function which requires looking back through all layers in the networkenables us to correctly update all layers in nn \n",
       "\n",
       "For f(x) = u(v(w(x))), the derivative of f(x) is $\\frac{d f}{d x}=\\frac{d u}{d v} \\cdot \\frac{d v}{d w} \\cdot \\frac{d w}{d x}$\n",
       "\n",
       "## Module 13 Definitions\n",
       "* **Concept** - definition\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "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))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "RYESi2kMybL8"
   },
   "source": [
    "# Module 14 - Natural Language Processing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 132,
   "metadata": {
    "id": "qIRJ4YYCzNHL"
   },
   "outputs": [],
   "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",
    "equation48=r\"\"\"$$\"\"\"\n",
    "equation49=r\"\"\"$$\"\"\"\n",
    "equation50=r\"\"\"$$\"\"\"\n",
    "equation51=r\"\"\"$$\"\"\"\n",
    "equation52=r\"\"\"$$\"\"\"\n",
    "\n",
    "\n",
    "# Lecture notes \n",
    "module14_lecture_notes = \"\"\"\n",
    "Neural LM associate each word in the vocabulary with a vector representation, creating a notion of similarity between words. \n",
    "Express the joint probability probability function of a word sequence in terms of the word vectors for the words in that sequence. \n",
    "simutaneously learn the word vectors and the parameters of the function.\\n\n",
    "\\n\n",
    "Neural language models is slower to train than n-gram, but have below advantages: \\n\n",
    "1. does not need smoothing \n",
    "2. can handle longer histories, large N \n",
    "3. can generalize over contexts of similar words, for example, after see blue, gree, can score green car after observe blue car \n",
    "4. higher accuracy \n",
    "\\n\n",
    "The input to NN is a k-gram of words w1:k.\\n\n",
    "The output is a probability disctribution over the next word. \\n\n",
    "k context words are treated as a word window and each word is associated with an embedding vector. \\n\n",
    "Input vector x just concatenates v(w) for each of the k words.\\n\n",
    "While training, the identities of the first k-1 words are used as features and the last word is used as target label for the classification. \n",
    "The model is trained using cross-entropy loss. \\n \n",
    "We can construnct a table that store observed sequence to look up the probability of seeing a word given a history. \\n\n",
    "When we have a new unseen sequence we can back-off, smoothing or interpolation. \\n\n",
    "We can also generalizing like bedroom vs room. \\n\n",
    "\\n\n",
    "We also want to represent the mearning of a word like synonyms, antonyms, connotations, sematic roles, entailment. \\n\n",
    "In vector space model each column vector represents a document, each row vector represents a term, \n",
    "and the value in a cell is based on how ofter that term occurred in that document. The length of the document vectors is the size of the vocabulary.\n",
    "Document vector will be sparsed and we can measure how similar two documents are by comparing their column vectors. \\n\n",
    "\\n\n",
    "In a term-term matrix, or a term-context matrix, the length of the vector is now |V| instead of number of documents. \n",
    "The value in a cell indicates how often A(row) in a context window surrounding by B (col). \\n\n",
    "We can look at a window of +/- n words, or using more complex contexts like dependency patterns, subj-of-verb, adj-mod, obj-of-verb, etc. \\n\n",
    "Raw word frequency is also not a great measure of association between words, because \"the\" and \"of\" will be very skewed. We want to measure whether a context word is informative about the target word, so we can use TF-IDF or PPMI. \\n\n",
    "TF-IDF=term frequency (how oftern a word occurred in a document)*inverse document frequency (1/number of documents that if occurred in) \\n\n",
    "We prefer dense vectors over sparse vectors, because its easy to use as features with fewer weights to tune, generalize bettern, and capture synonymy better. \n",
    "We can train a classifier to get that: \\n\n",
    "1. Treat the target word and a neighboring context word as positive examples \n",
    "2. Randomly sample other words in the lexicon to get negative samples \n",
    "3. use logistic regression to train a classifier to distinguish these two cases \n",
    "4. use the weights as embeddings \n",
    "\n",
    "For example, Word2vec instead of counting how often each word w occurs near \"A\", it trains a classifier on a binary prediction to predict is w likely to show up near \"A\" through skip-gram algorithms: \\n\n",
    "1. Treat the target word and a neighboring context word as positive examples. \n",
    "2. Randomly sample other words in the lexicon to get negative samples \n",
    "3. Use logistic regression to train a classifier to distinguish those two cases \n",
    "4. Use the weights as the embeddings \n",
    "\n",
    "\n",
    " \"\"\"\n",
    "\n",
    "# Definitions\n",
    "module14_definitions = {\n",
    "\"concept\" : \"definition\",    \n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 133,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 2008
    },
    "id": "lXNcHuKjyNXa",
    "outputId": "9387fac4-8a1d-4b3c-e465-fe1f5c83de35"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 14: Natural Language Processing\n",
       "## SLP Chapter 9.1 Language Models Revisited\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 9.2 Recurrent Neural Networks\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 9.3 RNNs as Language Models\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.1 Lexical Semantics\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.2 Vector Semantics\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.3 Words and Vectors\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.4 Cosine for measuring similarity\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.8 Word2vec\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.10 Semantic properties of embeddings\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.11 Bias and Embeddings\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.12 Evaluating Vector Models\n",
       " Your summary here \n",
       "\n",
       "## Module 14 Lecture Notes\n",
       "\n",
       "Neural LM associate each word in the vocabulary with a vector representation, creating a notion of similarity between words. \n",
       "Express the joint probability probability function of a word sequence in terms of the word vectors for the words in that sequence. \n",
       "simutaneously learn the word vectors and the parameters of the function.\n",
       "\n",
       "\n",
       "\n",
       "Neural language models is slower to train than n-gram, but have below advantages: \n",
       "\n",
       "1. does not need smoothing \n",
       "2. can handle longer histories, large N \n",
       "3. can generalize over contexts of similar words, for example, after see blue, gree, can score green car after observe blue car \n",
       "4. higher accuracy \n",
       "\n",
       "\n",
       "The input to NN is a k-gram of words w1:k.\n",
       "\n",
       "The output is a probability disctribution over the next word. \n",
       "\n",
       "k context words are treated as a word window and each word is associated with an embedding vector. \n",
       "\n",
       "Input vector x just concatenates v(w) for each of the k words.\n",
       "\n",
       "While training, the identities of the first k-1 words are used as features and the last word is used as target label for the classification. \n",
       "The model is trained using cross-entropy loss. \n",
       " \n",
       "We can construnct a table that store observed sequence to look up the probability of seeing a word given a history. \n",
       "\n",
       "When we have a new unseen sequence we can back-off, smoothing or interpolation. \n",
       "\n",
       "We can also generalizing like bedroom vs room. \n",
       "\n",
       "\n",
       "\n",
       "We also want to represent the mearning of a word like synonyms, antonyms, connotations, sematic roles, entailment. \n",
       "\n",
       "In vector space model each column vector represents a document, each row vector represents a term, \n",
       "and the value in a cell is based on how ofter that term occurred in that document. The length of the document vectors is the size of the vocabulary.\n",
       "Document vector will be sparsed and we can measure how similar two documents are by comparing their column vectors. \n",
       "\n",
       "\n",
       "\n",
       "In a term-term matrix, or a term-context matrix, the length of the vector is now |V| instead of number of documents. \n",
       "The value in a cell indicates how often A(row) in a context window surrounding by B (col). \n",
       "\n",
       "We can look at a window of +/- n words, or using more complex contexts like dependency patterns, subj-of-verb, adj-mod, obj-of-verb, etc. \n",
       "\n",
       "Raw word frequency is also not a great measure of association between words, because \"the\" and \"of\" will be very skewed. We want to measure whether a context word is informative about the target word, so we can use TF-IDF or PPMI. \n",
       "\n",
       "TF-IDF=term frequency (how oftern a word occurred in a document)*inverse document frequency (1/number of documents that if occurred in) \n",
       "\n",
       "We prefer dense vectors over sparse vectors, because its easy to use as features with fewer weights to tune, generalize bettern, and capture synonymy better. \n",
       "We can train a classifier to get that: \n",
       "\n",
       "1. Treat the target word and a neighboring context word as positive examples \n",
       "2. Randomly sample other words in the lexicon to get negative samples \n",
       "3. use logistic regression to train a classifier to distinguish these two cases \n",
       "4. use the weights as embeddings \n",
       "\n",
       "For example, Word2vec instead of counting how often each word w occurs near \"A\", it trains a classifier on a binary prediction to predict is w likely to show up near \"A\" through skip-gram algorithms: \n",
       "\n",
       "1. Treat the target word and a neighboring context word as positive examples. \n",
       "2. Randomly sample other words in the lexicon to get negative samples \n",
       "3. Use logistic regression to train a classifier to distinguish those two cases \n",
       "4. Use the weights as the embeddings \n",
       "\n",
       "\n",
       " \n",
       "\n",
       "## Module 14 Definitions\n",
       "* **Concept** - definition\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "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))"
   ]
  },
  {
   "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",
   "execution_count": 134,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 16218
    },
    "id": "T3cm1WV542_a",
    "outputId": "aae27dac-579c-45b9-a386-10abd28afaef"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 8: Markov Decision Processes\n",
       "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
       " \n",
       "The agents has some available actions “a” and P(s) to possible states “s”.\n",
       "\n",
       "Transition model P(s’|s,a) the probability that action a in state s reaches state s’ \n",
       "\n",
       "Decision theory deals with choosing among actions based on the desirability of their immediate outcomes, which means the environment is assumed to be episodic \n",
       "\n",
       "Utility function U(s) assign a single number to express the desirability of a state \n",
       "\n",
       "The expected utility of an action EU(a) is just the average utility value of the outcomes \n",
       " $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(RESULT(a)=s')U(s')$ \n",
       "\n",
       " The principle of maximum expected utility (MEU): a rational agent should choose that action that maximizes the agent’s expected utility: action = argmax EU(a) \n",
       "\n",
       "However, an agent may not know human’s true utility function, so decision theory is just a basic math framework to define AI problem not a panacea. \n",
       " \n",
       "\n",
       "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
       " \n",
       "The agent’s preference \n",
       "\n",
       "1.  A ≻ B the agent prefers A over B \n",
       "2.  A ∼ B the agent is indifferent between them \n",
       "\n",
       "We think of outcomes for every action as a lottery and there are 6 axioms of utility theory about preferences \n",
       "\n",
       "Orderability: a rational agent cannot refuse to decide, it can only prefer one or indifferent \n",
       "\n",
       "Exactly one of (A ≻ B), (B ≻ A), or (A ∼ B) holds. \n",
       "\n",
       "Transitivity: \n",
       "\n",
       "(A ≻ B) ∧ (B ≻ C) ⇒ (A ≻ C) \n",
       "\n",
       "Continuity: if B is between A and C in preference, then there is some probability P that the rational agent will be indifferent between getting B for sure and the lottery that yields A with probability p and C with probability 1-p \n",
       "\n",
       "A ≻ B ≻ C ⇒ ∃ p  [p,A; 1 − p,C] ∼ B \n",
       "\n",
       "Substitutability: if an agent is indifferent between two lotteries A,B then it is indifferent between two more lotteries that are the same except B is substituted for A \n",
       "\n",
       "A ∼ B ⇒ [p,A; 1 − p,C] ∼ [p,B; 1 − p,C]  can also change ~ to ≻ \n",
       "\n",
       "Monotonicity: if two lottery has outcomes A and B, if an agent prefers A to B, then it mush prefer the lottery that has a higher probability for A \n",
       "\n",
       "A ≻ B ⇒ (p > q   ⇔   [p,A; 1 − p,B] ≻ [q,A; 1 − q,B]) \n",
       "\n",
       "Decomposability: compound lotteries can be reduced to simpler ones using the law of probability, no gambling \n",
       "\n",
       "The 6 axions derive following additional  consequences: \n",
       "\n",
       "Existence of utility function: there exists U such that  \n",
       "\n",
       "U(A) > U(B)   ⇔   A ≻ B and U(A) = U(B)   ⇔   A ∼ B \n",
       "\n",
       "The agent’s behavior will not change if U′(S) = aU(S) + b \n",
       "\n",
       "Expected utility of a lottery: is the sum of the probability of each outcome times the utility of that outcome \n",
       "\n",
       "U([p1, S1;…; pn, Sn]) =ΣpiU(Si) \n",
       "\n",
       " \n",
       "\n",
       "## AIMA Chapter 16.3 Utility Functions\n",
       " \n",
       "If we want to build AI that helps a human to make decision, we must figure out human’s utility function. The process is called preference elicitation which involves listing choices and use the preference to derive utility function.  \n",
       "\n",
       "Normalized utilities: use a scale u⊥ = 0 u⊤ = 1, the agent will choose between S, a particular prize, and lottery [p, u⊤; (1 − p), u⊥], p is adjusted until the agent is indifferent S and lottery. Once this is done for each prize, the utilities for all lotteries involving those prizes are determined \n",
       "\n",
       "One value to represent people’s life is micromort, which is a million chance of death. \n",
       "\n",
       "Another measure is QALU, or quality adjusted life year. People are willing to accept a shorter life expectancy to avoid a disability. \n",
       "\n",
       "\n",
       "\n",
       "Utility of money: \n",
       "\n",
       "1. EMV is the expected monetary value \n",
       "2. The utility of money was proportional to the log of the amount based on Grayson study. most people have a utility function that is concave for positive wealth, or risk averse, people prefer a sure thing with a payoff that is less than the EMV of a gamble. Looking at the positive part of the curve, U(L) < U(SEMV (L)).\n",
       "3. However, in the negative wealth, people tend to be risk seeking.\n",
       "4. The difference between the EMV and its certainty equivalent is called insurance premium, which insurance industry believes the premium is positive.\n",
       "5. Linear curve is risk neutral \n",
       "\n",
       "In reality, we usually under estimate. \n",
       "\n",
       "A rational agent should act based on a normative theory, but actual agent acts with descriptive theory, explained by certainty effect that people are attracted to gains that are certain. People dislike ambiguity aversion (1/3 vs 2/3), and like framing effect (90% survival rate vs 10% death rate), prefer anchoring effect ($200 vs $50 with relative utility judgement) \n",
       " \n",
       "\n",
       "## AIMA Chapter 17.1 Sequential Decision Problems\n",
       " \n",
       "Several rules: \n",
       "\n",
       "The environment is fully observable \n",
       "\n",
       "But not deterministic \n",
       "\n",
       "If the agent bumps into a wall, it stays in the same square \n",
       "\n",
       "The transition model describes the outcome of each action in each state. Because the outcome is stochastic, T(s,a,s’) represents the probability of reaching state s’ if action a is done in state s. \n",
       "\n",
       "Assume the transitions are Markovian, the probability of reaching s’ from s depends only on s and not on the history of earlier states \n",
       "\n",
       "The utility function depends on a sequence of states and actions, or an environment history, not a single state. \n",
       "\n",
       "The reward function is R(s,a,s’) which is the transition from s to s’ through action a \n",
       "\n",
       "\n",
       "\n",
       "This is a MDP which is a sequential decision problem for a fully observable, stochastic environment with a Markovian transition and additive rewards. \n",
       "\n",
       "The solution is called a policy, or π, π(s) is the action recommended by the policy π for state s \n",
       "\n",
       "Policy is measured by the expected utility, so an optimal policy is a policy that yields the highest expected utility. \n",
       "\n",
       "A policy depends on time is called nonstationary, or finite horizon. In our example, we deal with infinite horizon, which is simpler because the agent can behave the same in the same state at different time. \n",
       "\n",
       "To calculate the utility of state, we use additive discounted rewards with a discount factor γ between 0-1, which shows agent’s preference of current rewards over future’s. Close to 0 means the agent wants immediate reward and close 1 means agent wants future rewards.  \n",
       "\n",
       "\n",
       "\n",
       "Why additive discounted rewards make sense? \n",
       "\n",
       "Both human and animals value near-term rewards more \n",
       "\n",
       "If rewards are monetary, its between to get it sooner than later \n",
       "\n",
       "True rewards is uncertain, they may never arrive \n",
       "\n",
       "Agent’s preferences between sequences are stationary, if you prefer one future to another starting tomorrow, then you should still prefer that future if it were to start today.\n",
       "It can remove some infinities. \n",
       "\n",
       "If γ<1 and rewards are bounded by +/-Rmax then by geometric series Uh=Rmax/(1-γ) \n",
       "\n",
       "If the environment contains terminal state and agent is guaranteed to get to one eventually, we will never need to compare infinite sequences with a proper policy \n",
       "\n",
       "Infinite sequences can be compared in terms of the average reward obtained per time step \n",
       "\n",
       "\n",
       "\n",
       "We can compare policies by comparing their expected utilities, the utility of a state is given by the Bellman equation: \n",
       " $U(s) = max\\sum_s P(s'|s,a)[R(s,a,s')+γU(s')]$ \n",
       "\n",
       "Another quantity is action-utility function, or the Q function Q(s,a) is the expected utility of taking a given action in a given state: \n",
       "U(s) = max Q(s,a)\n",
       "Bellman equation for Q value:\n",
       " $Q(s,a) = max\\sum_s P(s'|s,a)[R(s,a,s')+γmaxQ(s',a')]$ \n",
       "\n",
       "Based on the shaping theorem, To represent MDP, the best way to represet P and R is with sparse 3D tables \n",
       "\n",
       " \n",
       "\n",
       "## AIMA Chapter 17.2 Algorithms for MDPs\n",
       "\n",
       "Four ways to solve MDP: \n",
       "1. Value iteration \n",
       "\n",
       "Based on Bellman equation, if there are n states then there are n Bellman equations. \n",
       "\n",
       "The problem is the equations are nonlinear \n",
       "\n",
       "Can try iterative approach, start with arbitrary initial values for the utilities, calculate the right hand side of the equation, and plug it to the left hand side, updating the utility of each state from the utilities of its neighbors. Keep repeating until reach an equilibrium \n",
       "\n",
       "This is not linear \n",
       "2. Policy iteration \n",
       "\n",
       "Policy evaluation: Give a policy π, calculate Ui = U^πi , which is the utility of each state if πi executes \n",
       "\n",
       "Policy improvement: calculate a new MEU policy πi+1 with one-step look-ahead based in Ui \n",
       "\n",
       "The algorithm terminates when policy improvement step yields no change in the utilities. \n",
       "\n",
       "This is linear \n",
       "\n",
       "In each iteration, we can pick any subset of states and apply either kind of updating which is called asynchronous policy iteration \n",
       "3. Linear programing \n",
       "\n",
       "The basic idea is to consider as variables in the LP the utilities of each state s, noting that the utilities for an optimal policy are the highest utilities attainable that are consistent with the Bellman equations\n",
       "4. Online algorithms \n",
       "\n",
       "Value iteration and policy iteration are offline algorithms which generate optimal solution for a simple agent \n",
       "\n",
       "One solution to the online algorithm is a simplification of the expected min-max with rewards on nonterminal states. \n",
       "\n",
       "Another approach is real-time dynamic programming, for moderate-sized domains like grid worlds. It is not suitable for large domain before explored statins contain few repeated domains, so expect-max tree is better. Also if a reward is sparse, a simple heuristic for frontier nodes is not enough to guide the agent. \n",
       " \n",
       "\n",
       "## Module 8 Lecture Notes\n",
       " \n",
       "Stochastic/Markovian transition model: P(s'|s,a) which is the probability of arriving in state s' given that we are in state s and we selected action a. \n",
       "\n",
       "For this model, the agent has a utility or reward function which can be bounded positive or negative value. \n",
       "\n",
       "MDP is sequencial dicision problem in a fully observable environment with a stochastic transition model that has additive rewards, so we need to specify the utility function on a sequence of states and actions, the agent can receive reward at each time step which is additive, not just at goal state, based on transition from s to s' throught a R(s,a,s') \n",
       "\n",
       "Because MDP are non-determinstic, so we can solve it throught expectimax. \n",
       "\n",
       "We need to define following elements for MDP: \n",
       "1. a set of states S \n",
       "2. a set of actions A \n",
       "3. a transition function T(s,a,s'), probability/model that executiong a in s leading to s': P(s'|s,a) \n",
       "4. a reward function R(s,a,s'), sometimes R(s) or R(s') \n",
       "5. an initial state s0 \n",
       "6. optionally, 1+ terminal states \n",
       "\n",
       "The solution of MDP is the policy that maps a state to an action π(s)=a The same policy executed multiple times may have different reward, so we need to compute expected utility of all paths generated by a policy \n",
       "\n",
       "To give utility of sequences, we will give discount factor γ each time descend a level that\n",
       "1. makes sooner rewards higher utility than later rewards and \n",
       "2. help our algo converge. \n",
       "\n",
       "If the gave last forever with infinite utilities, we can \n",
       "1. like depth-limited-search, terminate eposides after fixed steps \n",
       "2. use 0<γ<1 \n",
       "3. absorbing state and guarantee a terminal state will be met. \n",
       "\n",
       "To solve expectimax search tree, we defines \n",
       "1. The utility of a state s: V(s) is the optimal expected utility in s\n",
       " $V*(s) = maxQ*(s,a)$ \n",
       "2. The utility of a q-state: Q(s,a) is the optimal expected utility taking action a from s \n",
       " $Q*(s,a) = \\sum_s T(s,a,s')[R(s,a,s')+γV*(s')]$ \n",
       "3. Optimal policy π(s) is the optimal action from state s \n",
       "\n",
       "First way to solve MDP is value iteration: \n",
       "\n",
       "For each state V*(s) repeat until convergence, time complexity for each iteration is O(S^2*A) \n",
       " $Vk+1(s) = max\\sum_s T(s,a,s')[R(s,a,s')+γVk(s')]$ \n",
       "This and 1 and 2 are bellman equations which can be simplfied as take correct first action and keep being optimal \n",
       "\n",
       "The problem with value iteration is that it is slow, the max at each state rarely change and policy converge before values. \n",
       "\n",
       "Contraction is part of the proof of convergence for value iteration algo\n",
       "\n",
       "\n",
       "\n",
       "Second way to slove MDP is policy iteration: \n",
       "\n",
       "We will first compute the utility of a state under a fixed(non-optimal) policy until convergence, time complexity for each iteration os O(s^2), the bellman equation now becomes  $Vπ(s) = \\sum_s T(s,π(s),s')[R(s,π(s),s')+γVπ(s')]$ \n",
       "\n",
       "Then update policy using one-step-look-ahead/bellman with converged utilities. Repeat steps until policy converges. \n",
       " $πi+1(s) = arg max\\sum_s T(s,π(s),s')[R(s,π(s),s')+γVπ(s')]$ \n",
       " \n",
       "\n",
       " \n",
       "\n",
       "## Module 8 Definitions\n",
       "* **Policy** - possible actions for each state\n",
       "* **Utility function** - total of discounted rewards or just rewards\n",
       "* **Expected utility** - your definition here\n",
       "* **Etc.** - your definition here\n",
       "\n",
       "\n",
       "# Module 9: Reinforcement Learning\n",
       "## AIMA Chapter 17.3 Bandit Problems\n",
       " \n",
       "The n-armed bandit is a formal model for real problems like deciding n possible investments. \n",
       "\n",
       "The optimal policy does not settle on the best arm in the long run, it could settle on a suboptimal arm  \n",
       "\n",
       "To define bandit problem: \n",
       "\n",
       "1. Each arm Mi is a MDP with only 1 possible action ai. The arm defines a distribution over sequences of rewards Ri,0, R,i,1,…, each Ri,t is random. \n",
       "2. The state space is the cartesian product S=S1*…*Sn \n",
       "3. One-arm bandit is when the result is equal to one arm M that produce R0, R1, R2… and cost λ for each pull\n",
       "4. If you pull arm for T times, the stopping time is T \n",
       "5. Gittin index of M provides a very simple optimal policy for any bandit probem: pull the arm that has the highest Gittin index then update the Gittin indices \n",
       "6. First decision takes O(n), latter decision cost O(1) \n",
       "7. Simplest and best known bandit problem is the Bernoulli bandit, where each arm has reward of 0 or 1. It also has a exploration bonus for arms that only been tried for a few times \n",
       " \n",
       "\n",
       "## AIMA Chapter 22.1 Learning from Rewards\n",
       " \n",
       "RL agent interacts with the environment and receive rewards based on its performance. For example, with MDP, the agent does not know the transition model or reward function, the agent needs to act to learn. \n",
       "\n",
       "Providing a reward to the agent is easier than give it example of how to perform because the reward function is concise and easy to define. We also don’t have to give correct action in any situation. \n",
       "\n",
       "A sparse rewards is win/loss because it has no informative reward signal. Some examples are chess and racing.\n",
       "\n",
       "We will learn five category of algorithms\n",
       "\n",
       "1. Model-based reinforcement learning: the agent uses a transition model of the environment to help interpret the reward signals and make decision. The transition model may be known like chess rule, or unknown. \n",
       "2. Model-free reinforcement learning: the agent neither knows nor learns a transition model. It learns a more direct way to behave. \n",
       "Action-utility learning, like Q-learning, which denote the sum of rewards from state s onward if action a is taken. The agent choose action with the highest Q value. \n",
       "Policy-search: the agent learns a policy π that maps states to actions like reflex agent. \n",
       "3. Passive reinforcement learning: agent’s policy is fixed and the task is to learn the utilities of states. \n",
       "4. Active reinforcement learning: agent also need to figure out what to do through exploration. An agent must experience as much as possible of the environment to learn how to behave. \n",
       "5. Inductive learning: agent can learn faster form its experiences with approaches like providing intermediate pseudo rewards. \n",
       "6. Apprenticeship learning: training a learning agent using demonstrations instead of reward signals. \n",
       "\n",
       " \n",
       "\n",
       "## AIMA Chapter 22.2 Passive Reinforcement Learning\n",
       " \n",
       "Start with a simple case where a fully observable environment with a small number of actions and states and fixed policy π. The agent try to learn the utility function U is called passive learning agent. \n",
       "\n",
       "Passive learning task is similar to policy evaluation task, but the difference is the passive learning agent does not know the transition model P or reward function R. \n",
       "\n",
       "The agent will execute a set of trails using policy π \n",
       "\n",
       "The utility is defined to be the expected sum of discounted rewards obtained if policy π is followed \n",
       "\n",
       "Direct utility estimation: the utility of a state is defined as the expected total reward from that state onward. This reduced reinforcement learning to a standard supervised learning problem. It ignores an important constraint that the utility of a state is determined by the reward and expected utility of the successor states. It obeys the Bellman equations for a fixed policy \n",
       "\n",
       "Adaptive dynamic programming: takes advantage of the constraints among the utilities of states through learning the transition model and solving MDP through DP. For a passive learning agent, this means insert learned transition model and observed rewards into above equation to calculate the utilities of the states. \n",
       "\n",
       "Temporal-difference learning: another way is to use the observed transitions to adjust the utilities of the observed stats so that they agree with the constraint equations. Below is the TD equation. It does not learn as fast as the ADP agent but it’s much simpler and require less computation. α is the learning rate parameter. TD does not need a transition model to perform update. \n",
       "\n",
       "ADP and TD are very similar, both try to make adjustment to the utility function and have each state agree with successors. The difference is that TD adjust a state to agree with its observed successor but ADP agree with all successors. This difference disappears when the effect of TD adjustments are averaged over a large number of transactions. Another difference is that TD makes a single adjustment per transition and ADP makes as many as it needs. From TD’s view, each adjustment ADP make is a result of pseudo-experience generated by simulating the current transition model. TD agent can also generate a large number of imaginary transitions, so the resulting utility estimates will approximate more and more closely to ADP. \n",
       "\n",
       "One can also use a heuristic to rank possible adjustments and carry out the important ones. For example the prioritized sweeping heuristic prefers to make adjustments to stats whose successors have just undergone a large adjustment. With these heuristics approximate ADP can learn almost as fast as full ADP. They can then handle state spaces are too large for full ADP \n",
       "\n",
       " \n",
       "\n",
       "## AIMA Chapter 22.3 Active Reinforcement Learning\n",
       " \n",
       "Passive learning agent has a fixed policy that determines its behavior, but active learning agent decide what actions to take. \n",
       "\n",
       "First the agent need to learn a complete transition model with outcome probabilities for all actions, next the agent has a choice of actions and the utilities it needs to learn are those defined by the optimal policy. So the agent need to obtain the utility function U using the value iteration or policy iteration algorithms. Finally with the utility function the agent can extract the optimal action by 1-step-look-ahead to pick the action maximizing the expected utility. \n",
       "\n",
       "\n",
       " \n",
       "Exploration \n",
       "\n",
       "1. Greedy agent greedily takes the actin that it currently believes to be optimal \n",
       "2. A GLIE (greedy in the limit of infinite exploration” scheme must try each action in each state unbounded number of times to avoid an optimal action being missed. The most simple one is to have the agent choose a random action at time step t with probability 1/t, otherwise follow the greedy policy. This is slow but will eventually converge. A better approach is to add some weight to actions that agent has not tried. Here f is the exploration function \n",
       "\n",
       "Safe exploration \n",
       "\n",
       "1. Not all actions are safe and some are irreversible. The worst case is entering an absorbing state where no actions have effect and no rewards are given. \n",
       "\n",
       "2. We cannot afford to enter these bad states in practical settings so a better idea is to choose a policy works reasonably well and close to true model. There are three math approaches \n",
       "Bayesian reinforcement learning: which assumes a prior probability P(h) over h about the true model. When agent decides to stop learning, the optimal policy is the one with highest utility \n",
       "\n",
       "Robust control theory allows a set of possible models H without assigning probabilities and defines an optimal robust policy which gives the best outcome in the worst case over H. It is like the minmax solution where adversary pick the worst possible result. The issue is the result is too conservative, so human can pre set a serious of actions so the system can act reasonably from the start and learn to improve. Human can also write down constraints on what a system can do and a program outside the learning system can enforce those constraints. \n",
       "\n",
       "Temporal-difference q-learnin \n",
       "\n",
       "It does not need a transition model P either for learning or for action selection. It also cannot look into the future, so its hard when rewards are hard and long actions sequences need to be constructed to reach them.\n",
       "\n",
       "Q-learning is an off-policy algo but SARSA is an on-policy algo.\n",
       "\n",
       "\n",
       "\n",
       "## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n",
       " \n",
       "Utility functions and Q-functions work for state space up tp 10^6, which is too slow for real-world environments. \n",
       "\n",
       "We can also use function approximation to approximate the true utility function or Q-function. \n",
       "\n",
       "Approximating direct utility function - It generates trajectories in the state space and extract the sum of rewards for each state. The state and sum of rewards received form a example for supervised learning. For reinforcement learning, its better to use an online learning algorithm that updates the parameter after each trial. \n",
       "\n",
       "\n",
       "Approximating temporal-difference learning\n",
       "\n",
       "1. We need to adjust the parameters to reduce temporal difference between successive states. \n",
       "2. When the function approximator is linear the update rule can converge close to true function for passive TD learning.\n",
       "3. For active learning and nonlinear functions like neural networks it does not work. The parameters can go to infinity. There is another problem called catastrophic forgetting when the agent has learned too well. One solution is experience replay where the learning algorithm can retain trajectories and replay to ensure its value function is still accurate to state space that it does not visit. \n",
       "4. For model-based reinforcement learning, function approximation can be helpful for meaning a model of the environment. Learning a model from an observable environment is a supervised learning problem. \n",
       "5. For a partially observable environment, the learning problem is harder because the next percept is not a label for the state prediction. \n",
       "\n",
       "Deep reinforcement learning \n",
       "\n",
       "1. There may be no good linear function to approximate utility function and we may not invent necessary features in new domains, so researchers explored more complex, nonlinear function approximators, like deep neural networks.\n",
       "2. Deep RL still have issues like hard to get good performance and the trained system may be have unpredictably if environment differ from the training data. \n",
       "\n",
       "Reward shaping - This involves supplying agent with additional rewards for making progress.\n",
       "\n",
       "Hierarchical reinforcement learning - Another way to solve long action sequence is to break them up into smaller pieces until the actin sequence are short enough to make learning easy. \n",
       "\n",
       " \n",
       "\n",
       "## Module 9 Lecture Notes\n",
       " \n",
       "Solving MDP is like offline planning because you do not actually play the game, you just know the details and determine all quantities through computation. \n",
       "\n",
       "Reinforcement learning involves below concepts:\n",
       "\n",
       "1. Exploration which means you have to try unknown action to get information \n",
       "2. Exploitation which means you have to use what you know eventually \n",
       "3. Regret which means you may make mistakes even after learning \n",
       "4. Sampling wihch means you need to try things repeatedly \n",
       "5. Difficulty which means learning is harder than solving MDP \n",
       "\n",
       "In reinforcement learning, the agent will receive feedback in form of rewards. Its utility is defined by the reward function and must learn to maximiaze rewards based on observed sample of outcomes. \n",
       "\n",
       "Compared with MDP it still has states S, actions A, model T, reward function R, looking for policy π, but does not know T or R. \n",
       "\n",
       "\n",
       "\n",
       "Model-Based Learing: learn the model based on experiences and solve for values assuming learned model were correct. \n",
       "\n",
       "1. count outcomes s' for each s, estimate T, and discover R when experience (s,a,s') \n",
       "2. solved the learned MDP as before \n",
       "\n",
       "Passive reinforcement learning: input a π, witout T and R learn the state values. This is online learning. \n",
       "\n",
       "\n",
       "\n",
       "Direct evalueation: compute values for each state under π by average observed sample values \n",
       "\n",
       "1. Pro is it does not need knowledge for T, R and compute correct average values \n",
       "2. Con is each state must be learned separately which takes long time and waste state connections \n",
       "\n",
       "Temporal Difference (TD) Learing: learn from evey experience. Decreasing learning rate can give converging averages and bigger α trust estimates more \n",
       "\n",
       "1. Sample of V(s): \n",
       " $ sample=R(s,π(s),s')+ γVπ(s')$ \n",
       "2. Update to V(s): \n",
       " $Vπ(s) = (1-α)Vπ(s)+(α)sample]$ \n",
       "3. TD is a model free way to evalue policy, like Bellman updates, we can try to learn Q values and make action selection model free\n",
       "\n",
       "Active reinforcement learning: without T and R, learner make choices. This is also online learning \n",
       "\n",
       "\n",
       "\n",
       "Q-Value iteration: start with Q0(s,a)=0 which is right, given Qk, calculate the depth k+1 q-values for all q-states: \n",
       " $Qk+1(s,a) = \\sum_s T(s,a,s')[R(s,a,s')+γmaxQk(s',a')]$ \n",
       "This coverges to optimal policy even if you are acting suboptimally, but you have to explore enough, eventually make the learning rate small enough but not decrease too fast \n",
       "\n",
       "\n",
       "\n",
       "To explore, we can do random: ε act radomly, ow current policy, but the problems is although eventually explore the space, keey thrashing around. We can lower ε over time or use a exploration functions.\n",
       "If an agent's explore function values curiositym N(s,a) will be low. Q learning can learn the optimal Q-function through off policy learningand not executing the optimal policy. \n",
       "Q learning will be come: \n",
       " $Q(s,a) = R(s,a,s')+γmax f(Q(s',a'),N(s',a'))$ \n",
       "\n",
       "\n",
       "Regret is a measure of your total mistake cost which includes the different between your expected rewards and optimal rewards. It quantifies the relative goodness of exploration procedures\n",
       "\n",
       "Basic Q learning keep a table of all q-values, which is too much to hold in memory. We can generalize it by learning small number of training states from experience and generalize that to new similar situations. \n",
       "\n",
       "Q(s,a)=w1f1(s,a)+w2f2(s,a)+...+wnfn(s,a) \n",
       "\n",
       "There might be cases that states with similar features but different values.\n",
       " \n",
       "\n",
       "## Module 9 Definitions\n",
       "* **Term** - your definition here\n",
       "\n",
       "\n",
       "# Module 10: Probabilies and Language Models\n",
       "## AIMA Chapter 12.1 Acting under Uncertainty\n",
       " \n",
       "Logical agents handle uncertainty by keep track of belief state which includes all possible world state and have a plan for every event. This works for simple problems but has drawbacks\n",
       "\n",
       "Agent must consider every possible event that its sensor observes, no matter how unlikely so it might keep a large belief-state with unlikely possibilities\n",
       "\n",
       "A correct contingent that handles every event can grow large with arbitrarily unlikely contingencies \n",
       "\n",
       "Sometime agent has to act when no plan is guaranteed to achieve goal yet. \n",
       "\n",
       "Toothache example \n",
       "\n",
       "1. Laziness: listing the complete set of antecedents requires an exceptionalness rule \n",
       "2. Theoretical ignorance: happens when there is no complete theory for the domain\n",
       "3. Practical ignorance: even if we know all rules we maybe not sure about a particular patient\n",
       "\n",
       "The agent can provide a degree of belief and we can use probability theory, which provides a way of summarizing uncertainty that comes from our laziness and ignorance\n",
       "\n",
       "To make choices, an agent must have preferences among different possible outcomes of the various plans, which can be utility theory. The utility theory states that every state as a degree of usefulness and the agent will prefer states with higher utility. \n",
       "\n",
       "Decision theory: Decision theory = probability theory + utility theory \n",
       "\n",
       "Maximum expected utility: an agent is rational iff it chooses the action that yields the highest expected utility averaged over all possible outcomes \n",
       "\n",
       "\n",
       " \n",
       "\n",
       "## AIMA Chapter 12.2 Basic Probability Notation\n",
       " \n",
       "Probability assertions talk about how probable the various worlds are. All possible world sets is a sample space. Possible words are mutually exclusive and exhaustive \n",
       "\n",
       "A fully specified probability model associates a numerical probability with each possible world. \n",
       "\n",
       "The basic axion of probability theory states that every possible works has a P between 0 and 1, the total probability is :\n",
       "$0 \\leq P(\\omega) \\leq 1 \\text { for every } \\omega \\text { and } \\sum_{\\omega \\in \\Omega} P(\\omega)=1$\n",
       "\n",
       "\n",
       "The probability associated with a proposition is defined to be the sum of probabilities of words in which it holds. For example: P(11)=P(5,6)+P(6,5) \n",
       "\n",
       "For situations of prior probabilities: \n",
       "$P(a \\mid b)=\\frac{P(a \\wedge b)}{P(b)}$\n",
       "\n",
       "\n",
       "Product rule\n",
       "$P(a \\wedge b)=P(a \\mid b) P(b)$\n",
       "\n",
       "\n",
       "Variables in probability theory are random variables and begin with uppercase letter. Name for values are in lowercase. A boolean random variable has the range {true, false}. For discrete distribution we can have P(Weather) = ⟨0.6, 0.1, 0.29, 0.01⟩, for continuous distribution we can have P(NoonTemp = x) = Uniform(x; 18C, 26C), which is also called a probability density function. \n",
       "\n",
       "A possible world is defined to be an assignment of values to all of the random variables under considerations\n",
       "\n",
       "In addition to distribution on single variables, we also have notation for distributions on multiple variables using comma, for example, P(Weather, Cavity) denotes the probabilities of all combinations of values of Weather and Cavity. \n",
       "\n",
       "P(Weather,Cavity) = P(Weather |Cavity)P(Cavity)\n",
       "\n",
       "Full joint probability distribution: A probability model is completely determined  by the joint distribution for all of the random variables\n",
       "\n",
       "Probability axion:\n",
       "\n",
       "1. Negation: P(-a)=1-P(a)\n",
       "2. Inclusion-exclusion principle: P(a ∨ b) = P(a) + P(b) − P(a ∧ b)\n",
       " \n",
       "\n",
       "## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n",
       " \n",
       "Marginalization/summing out: sum up the probabilities for each possible value of the other variables and taking them out of the equation $\\mathbf{P}(\\mathbf{Y})=\\sum_{\\mathbf{z}} \\mathbf{P}(\\mathbf{Y}, \\mathbf{Z}=\\mathbf{z})$\n",
       "\n",
       "\n",
       "Conditioning:\n",
       "$\\mathbf{P}(\\mathbf{Y})=\\sum_{\\mathbf{Z}} \\mathbf{P}(\\mathbf{Y} \\mid \\mathbf{Z}) P(\\mathbf{Z})$\n",
       "\n",
       "## AIMA Chapter 12.4 Independence\n",
       " \n",
       "If a and b are independent \n",
       "\n",
       "\tP(a | b) = P(a) or P(b | a) = P(b) or P(a ∧ b) = P(a)P(b) \n",
       "\n",
       "\tP(X| Y ) = P(X) or P(Y |X) = P(Y ) or P(X, Y ) = P(X)P(Y ). \n",
       "\n",
       "## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n",
       " \n",
       "Basic Eequation: $P(b \\mid a)=\\frac{P(a \\mid b) P(b)}{P(a)}$\n",
       "\n",
       "\n",
       "Adding an evidence e: $\\mathbf{P}(Y \\mid X, \\mathbf{e})=\\frac{\\mathbf{P}(X \\mid Y, \\mathbf{e}) \\mathbf{P}(Y \\mid \\mathbf{e})}{\\mathbf{P}(X \\mid \\mathbf{e})}$\n",
       "\n",
       "\n",
       "General Bayes rule with normalization \n",
       "\n",
       "\tP(Y|X) = αP(X|Y)P(Y) \n",
       "\n",
       "\tα is the normalization constant that makes the entries in P(Y|X) sum to 1 \n",
       "\n",
       "With a third variable Z, the conditional independence becomes \n",
       "\n",
       "\tP(X, Y|Z) = P(X|Z)P(Y|Z). \n",
       "\n",
       "\n",
       " \n",
       "\n",
       "## AIMA Chapter 12.6 Naive Bayes Models\n",
       " A single cause can directly influences a number of effects that are conditionally independent. \n",
       "This is called a naive Bayes model because the effect variables are not strictly independent. $\\mathbf{P}\\left(\\text { Cause, Effect }_{1}, \\ldots, \\text { Effect }_{n}\\right)=\\mathbf{P}(\\text { Cause }) \\prod_{i} \\mathbf{P}\\left(\\text { Effect }_{i} \\mid \\text { Cause }\\right)$ \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",
       "Axiom of probability: \n",
       "\n",
       "1. The probability is always include 0 and 1 \n",
       "2. The probability of all possible worlds is 1 \n",
       "\n",
       "Marginal distributions are sub-tables with eliminate variables. \n",
       "\n",
       "Conditional probabilities: $P(a \\mid b)=\\frac{P(a, b)}{P(b)}$\n",
       "\n",
       "\n",
       "Probabilistic inference is to compute a desired probability from other known probabilities \n",
       "\n",
       "The product rule: $P(y) P(x \\mid y)=P(x, y)$\n",
       "\n",
       "\n",
       "The chain rule: $P\\left(x_{1}, x_{2}, x_{3}\\right)=P\\left(x_{1}\\right) P\\left(x_{2} \\mid x_{1}\\right) P\\left(x_{3} \\mid x_{1}, x_{2}\\right)$ There are N! way to apply chain rule to a joint distribution with N variables\n",
       "\n",
       "\n",
       "$P\\left(x_{1}, x_{2}, \\ldots x_{n}\\right)=\\prod_{i} P\\left(x_{i} \\mid x_{1} \\ldots x_{i-1}\\right)$\n",
       "\n",
       "\n",
       "Baye's rule: P(x,y)=P(x|y)P(y)=P(y|x)P(x) \n",
       "\n",
       "For example P(\"the underdog Philly\")=P(the) * P(underdog|the) * P(Philly|the underdog) \n",
       "\n",
       "Markov assumption, or simple assumption, n-gram model simplfy this by only depends on the previous k words, not the whole context, \n",
       "or given the present state, future and past are independent. It makes it possible to estimate the probabilities from data. \n",
       "If it is a bigram model, then the probability of a word is determined only by a single preceding word.\n",
       "\n",
       "\n",
       "The goal of Probablistic language model is to assign a probability to a sentence which can solve problems like autocompletion for texting, machine translation,\n",
       "spelling correction, and speech recognition, summerization, question-answering, dialog systems. \n",
       "\n",
       "Related tasks include calculate the probability of an upcoming word\n",
       " \n",
       "A language model (LM) calculate either of the above, P(W) or P(Wn|W1,W2,...Wn-1) \n",
       "\n",
       "To construct a dynamic bayesian model, we need the sensor model, transition model, and prior distribution over the state variables.  \n",
       "\n",
       "Ngram model is typically evaluated by perplexity on a test set.\n",
       "\n",
       " \n",
       "\n",
       "## Module 10 Definitions\n",
       "* **Term** - your definition here\n",
       "\n",
       "\n",
       "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n",
       "## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n",
       " Your summary here \n",
       "\n",
       "## AIMA 13.3 Exact Inference in Bayesian Networks\n",
       " Your summary here \n",
       "\n",
       "## Module 11 Lecture Notes\n",
       " \n",
       "Two variables are independent if $\\forall x, y: P(x, y)=P(x) P(y)$\n",
       "\n",
       "\n",
       "or $\\forall x, y: P(x \\mid y)=P(x)$\n",
       "\n",
       "\n",
       "Conditional independence happens when $\\forall x, y, z: P(x, y \\mid z)=P(x \\mid z) P(y \\mid z)$\n",
       "\n",
       "\n",
       "or $\\forall x, y, z: P(x \\mid z, y)=P(x \\mid z)$\n",
       "\n",
       "\n",
       "For example, P(detect|toothache,cavity)=P(detect|cavity) because detect is conditionally independent of toothache given cavity, toothache can be dropped\n",
       "\n",
       "Apply to chain rule, becuase traffic is independent of umbrella given rain so it can be dropped \n",
       "\n",
       "P(Traffic,Rain,Umbrella)=P(Rain)P(Traffic|Rain)P(Umbrella|Rain,Traffic)=P(Rain)P(Traffic|Rain)P(Umbrella|Rain) \n",
       "\n",
       "Baye's net is a graphical technique for discribing complex joint distribution models using simple,local distribution. It solves the problem of full joint distribution table that is too big and hard to estimate mutiple variables at the same time. \n",
       "\n",
       "Model is a directed, acyclic graph with a conditional distribution for each node. Or Bayes net=Topology(graph)+local conditional probability \n",
       "\n",
       "Model notation: nodes are variables and arcs are interactions, arrow means conditional independence, not casual. \n",
       "\n",
       "It implicitly encode joint distributions: $P\\left(x_{1}, x_{2}, \\ldots x_{n}\\right)=\\prod_{i=1}^{n} P\\left(x_{i} \\mid \\text { parents }\\left(X_{i}\\right)\\right)$\n",
       "\n",
       "\n",
       "The size of BN is O(N*2^(k+1)) with nodes have up to k parents, the size of joint distribution over N nodes is 2^N \n",
       "\n",
       "\n",
       "D-separation gives precisioe conditional independence guarantee from graph alone, but it may have further independence that is not detectable until inspection: \n",
       "\n",
       "1. X->Y->Z: X is not guaranteed independ of Z, but is conditionally independend of Z given Y, P(x,y,z)=P(x)P(y|x)P(z|y) \n",
       "2. Y->X and Y->Z, X is not guaranteed independ of Z, but is conditionally independend of Z given Y, P(x,y,z)=P(y)P(x|y)P(z|y) \n",
       "3. X->Z and Y->Z, X is independent of Y, but X and Y are not independent given Z \n",
       "\n",
       "To find reachability, we can shade the evidence node and look for path in the resulting graph: \n",
       "\n",
       "1. if X and Y are conditionally independent then there is no active path \n",
       "2. A path is active if each triple is active. \n",
       "3. a single inactive segment can block a path \n",
       " \n",
       "\n",
       "## Module 11 Definitions\n",
       "* **Concept** - definition\n",
       "\n",
       "\n",
       "# Module 12: Naive Bayes and Perceptrons\n",
       "## AIMA Chapter 19.1 Forms of Learning\n",
       " A computer agent learning is called machine learning, which it observes data, build a model based on the data, and use the model to solve problems. \n",
       "\n",
       "The improvent of agent program through machine depends on three factors, the first one is which component to be improved, the second one is what prior knowledge (that infuence the model) the agent has,\n",
       "and the data and feedback on the data. \n",
       "\n",
       "There are three types of learnings with three types of feedbacks: \n",
       "\n",
       "Supervised learning is when the agent a function that maps input to output through observations. Input can be pictures, output can be a label. \n",
       "\n",
       "Unsupervised learning is when agent tries to learn patterns without explicit feedback, like clustering. The agent tries to detect clusters for inputs. \n",
       "\n",
       "Reinforcement learning is when agent learns from a series of rewards and punishments. \n",
       "\n",
       "\n",
       "## AIMA Chapter 19.2 Supervised Learning\n",
       " \n",
       "The goal for supervised learning is to find a function h, which is called a hythothesis about the world, that approximate the true mapping function f.\n",
       "H is drawn from a hypothesis space of possible functions. \n",
       "\n",
       "Alternatively, h can represent a model of the data an H is a model class. \n",
       "\n",
       "To choose a hythothesis space, we can based on prior knowledge or exploratory data analysis \n",
       "\n",
       "Consistent hypothesis is when each xi in training set h(xi)=yi, whereas a best-fit match is each h(xi) close to yi. \n",
       "\n",
       "To measure h, we need to exam how well it handles unseen input using a test set. h generalizes well if predicts output of test sets well \n",
       "\n",
       "To analyze hypothesis space, we can look at bias and variance. Bias is regardless of the training set and measures the tendency of a predictive hypothesis to deviate\n",
       "from the expected value averaged over different traning sets. Bias is usually caused by hypothesis space restrictions. When hypothesis cannot find a pattern in data\n",
       "it is underfitting \n",
       " \n",
       "Variance is the amount if change in the hypothesis caused by fluctuation in the training data. Sometimes when a function fit a particular data set too well it may overfit\n",
       "and cannot predict unseen data very well. \n",
       "\n",
       "Bias-variance tradeoff happens when choosing between complex, low-bias hypotheses that fits the training data well and simpler and low-variance hypothese that generalize better. \n",
       "If a binary perceptron has a high bias values, it is easier for perceptron to output a 1.\n",
       " \n",
       "\n",
       "## AIMA Chapter 19.3 Learning Decision Trees\n",
       " \n",
       "A decision tree makes decision through making tests from root through a leaf. Internal nodes represent a test, the branch represents possible values of the attribute,\n",
       "amd the leaf nodes represents the value to be returned. \n",
       "\n",
       "Input and output can be discrete or continuous, a boolean input is discrete. It is the same as a logical statement: output=P1 V P2 V P3... \n",
       "\n",
       "No representation is good for all kinds of functions. \n",
       "\n",
       "Learn-Decision-Tree algorithm uses a greedy divide-and-conquer strategy which always tests the most important attribute first and recursively solve the smaller subproblems. In this way, the tree will be short and shallow. \n",
       "\n",
       "To measure the importance of the attribute, we can use entropy, which measures the uncertainty of a random variable. In another word, the more information, the less entropy. \n",
       "\n",
       "One way to solve overfitting is decision tree pruning which elimiates nodes that are not relevent. Irrelevence can be measured by information gain. \n",
       "\n",
       "Another way is called early stopping which combines X^2 pruning and information gain, which stop the decision tree from generating new nodes when it has no good attribute to split on. \n",
       "\n",
       "Decision tree is more useful when it can handle missing data, continuous and multivalued input attributes and continuous-valued output attribute.\n",
       " \n",
       "\n",
       "## AIMA Chapter 19.4 Model Selection and Optimization\n",
       " \n",
       "First we select stationarity assumption P(Ej) which makes future examples like the past. It has the same prior probability distribution and is independent of previous examples. \n",
       "Next we define optimal fit hypothesis which minimizes error rate. We estimate the error rate by measuring its performance on a test set. We usually divides data into training set which is used to train candidate models,\n",
       "validation set, also called development set or dev set, which is used to evaluate candidate models and choose the best one, and the test set which is used to conducting final evaluation and choose the best model. \n",
       "If we don't have enough data we can use k-fold cross validation. \n",
       "\n",
       "There are two steps to find a good hypothesis, model selection and optimization or training. \n",
       "\n",
       "For model selection, a learner takes a hyperparameter. It starts with the smallest size output a simple model and iterates to the larger sizes with complex models. \n",
       "Model selection will select the model which returns lowest average eeror on the held-out data. \n",
       " \n",
       "Machine learning will choose to minimize loss function rather than maximize utility function. \n",
       "\n",
       "Another approach to select model is regularization which penalize complex hypothesis. \n",
       "\n",
       "When there are multiple hyperparameters, or with continuous value, we can use grid search which try all combinations of values, or random search when there are too many combinations for hyperparameter tuning.\n",
       "\n",
       "\n",
       "## AIMA Chapter 19.5 The Theory of Learning\n",
       " \n",
       "The computational learning theory states that very wrong hypothesis will be discovered after some examples, so hypothesis with large training sets should be Probably Approximately Correct. \n",
       "\n",
       "To restrict the hypothesis without elimating the true function, we have three ways. The first way is to bring prior knowledge. The second way is to insist the algorithm returns a simple one. \n",
       "The third way focuses on learnable subsets and assumes that the restricted hypothesis spaces contains a h that is close to the true function f. \n",
       " \n",
       "\n",
       "## AIMA Chapter 19.6 Linear Regression and Classification\n",
       " \n",
       "Gradient descent is used to minimizing loss where we start with any point in the weight space, keep moving a small amount towards the steepest downhill direct until a local minimum. \n",
       "The step size is the learning rate. \n",
       " \n",
       "\n",
       "## SLP Chapter 4.1 Naive Bayes Classifiers\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.2 Training the Naive Bayes Classifier\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.3 Worked Example\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.6 Naive Bayes as a Language Model\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.8 Test sets and Cross-validation\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.9 Statistical Significance Testing\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.10 Avoiding Harms in Classification\n",
       " Your summary here \n",
       "\n",
       "## Module 12 Lecture Notes\n",
       " \n",
       "Machine learning is the process to acquire a model from data and experience, like classification, spam/fraud detection. \n",
       "\n",
       "For example, using Naive Bayes we can assume all features are independent effects of the label and try to learn $P\\left(Y, F_{1} \\ldots F_{n}\\right)=P(Y) \\prod_{i} P\\left(F_{i} \\mid Y\\right)$\n",
       "\n",
       "\n",
       "Naive bayes has two utilizations, \n",
       "\n",
       "The first is the inference method \n",
       "\n",
       "1. get joint probability of label and evidence for each label \n",
       "2. sum to get probability of evidence \n",
       "3. normalize by dividing Step 1 by step 2 \n",
       "\n",
       "The second is to estimate local conditional probability tables \n",
       "\n",
       "1. first calculate P(Y), the prior over labels \n",
       "2. calculate P(Fi|Y) for each feature \n",
       "\n",
       "To use NB for text, we follow below steps for bag-of-words, which the model is insensitive to word order: \n",
       "\n",
       "1. The feattures Wi is the word at position i \n",
       "2. We want to predict label conditioned on feature variables \n",
       "3. We assume features are conditionally independent given label \n",
       "4. Each Wi is identically distributed \n",
       "\n",
       "For ML model, we have below features: \n",
       "\n",
       "1. Data is separated into training set, held out set, and test set \n",
       "2. Features are attribute-value pairs which characterize each x \n",
       "3. Experiment cycle involves learning parameters on training set, tune hyperparameters on held-out data and compute accuracy on test sets \n",
       "4. Evaluation is to compute accuracy \n",
       "5. Prevent overfitting which fit the trainning data perfectly and improve generalization which needs to smooth or regularize the estimates\n",
       "  5.1 Normal estimate just use P=count(x)/total samples, but Laplace smoothing pretends to saw every outcome once more than actual $P_{L A P}(x)=\\frac{c(x)+1}{\\sum_{x}[c(x)+1]}$\n",
       "  5.2 or kth more than actual $P_{L A P, k}(x)=\\frac{c(x)+k}{N+k|X|}$\n",
       "  5.3 but Laplace perform poorly for P(X|Y) when X or Y is very large, so another option is linear interpolation $P_{L I N}(x \\mid y)=\\alpha \\widehat{P}(x \\mid y)+(1.0-\\alpha) \\widehat{P}(x)$\n",
       "6. If there are errors, more features are needed to be added as new variables in NB model. \n",
       "\n",
       "Perceptrons are inspired by human neurons. \n",
       "\n",
       "For linear classifiers inputs are feature values and each feature has a weight, the sum is the activation: $\\operatorname{activation}_{w}(x)=\\sum_{i} w_{i} \\cdot f_{i}(x)=w \\cdot f(x)$\n",
       "\n",
       "\n",
       "For binary perceptron case: \n",
       "\n",
       "1. start with weights =0 \n",
       "2. classify with current weights $y=\\left\\{\\begin{array}{ll}+1 & \\text { if } w \\cdot f(x) \\geq 0 \\n -1 & \\text { if } w \\cdot f(x)<0\\end{array}\\right.$\n",
       "3. If correct y=y* then no change, otherwise adjust the weight vector to  $w=w+y^{*} \\cdot f$\n",
       "\n",
       "For multi-class perceptron case: \n",
       "\n",
       "1. Start a weight vector for each class wy \n",
       "2. calculate score of a class y w_y*f(x) \n",
       "3. prediction with highest score wins \n",
       "4. if correct then no change \n",
       "5. if wrong then lower score of wrong answer, raise score of right answer w_y=w_y-f(x), w_y*=w_y*+f(x) \n",
       "\n",
       "Perceptron are separabable if some parameters get the training set perfectly correct. If it is separable it will eventually converge in binary case. \n",
       "\n",
       "Problems with perceptron includes when data is not separable weight will thrash. Overtraining may also lead to overfitting. \n",
       "\n",
       "To solve these problems we can use MIRA which adjust the weight update to mitigate effect by choosing an update to fix the current mistake but minimize the change to w $w_{y}=w_{y}^{\\prime}-\\tau f(x)$ and $\\tau^{*}=\\min \\left(\\frac{\\left(w_{y}^{\\prime}-w_{y^{*}}^{\\prime}\\right) \\cdot f+1}{2 f \\cdot f}, C\\right)$\n",
       "Giving a cap C can prevent updates to be too large and make converge faster on noisy data \n",
       "\n",
       "To decide which separation is better, a stategy is called SVM to maximize margin. \n",
       "\n",
       "In conclution, NB build a model with training data and give prediction probabilities. It uses strong assumptions about feature independence and perform once pass over the data. Perceptron makes less assumptions about the data.\n",
       "It is also mistake-driven learning and use multiple passes over the data lead to more accurate results. \n",
       "\n",
       "\n",
       "\n",
       "If the separator are non linear, the origional feature space can be mapped to some higher-dimentional feature space whenre training set is separable. \n",
       "\n",
       "Instead of using a linear activation function, we can also use a non-linear one, sigmoid(map output into range [0,1]), tanh(variant of sigmoid and maps outlier towards mean, or Rectified linear unit (ReLU) \n",
       "\n",
       "Parametric models has a fized size on the number of parameters \n",
       "\n",
       "\n",
       "## Module 12 Definitions\n",
       "* **Induction** - from sepecific observations to general rule, and the conclusion may be wrong\n",
       "* **Classification** - output is one of a set of values\n",
       "* **Regression** - output is a number\n",
       "* **Training set** - a list of input-output pairs\n",
       "* **Eda** - examing data with statistical tests and visualizations\n",
       "* **Decision tree** - a function that maps attributes to a single decision output\n",
       "* **Univariate linear function** - straight line function\n",
       "* **Linear regression** - find hw=w1x+w0\n",
       "* **Weight space** - all possible values of the weights\n",
       "* **Epoch** - a step that have all training data\n",
       "\n",
       "\n",
       "# Module 13: Neural Networks\n",
       "## SLP Chapter 5.1 Classification: the sigmoid\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 5.2 Learning in Logistic Regression\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 5.3 The cross-entropy loss function\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 5.4 Gradient Descent\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 5.5 Regularization\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 5.6 Multinomial logistic regression\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.1 Units\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.2 The XOR problem\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.3 Feedforward Neural Networks\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.5 Feedforward Neural Language Modeling\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.6 Training Neural Nets\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.7 Training the neural language model\n",
       " Your summary here \n",
       "\n",
       "## Module 13 Lecture Notes\n",
       " \n",
       "Classifier has following components: \n",
       "\n",
       "1. A feature representation of the input, for each input xi there is a vector of features [x1,x2,...xn] \n",
       "2. A classification function that computes estimated y \n",
       "3. An objective function for learning that involves minimizing errors \n",
       "4. An algorithm for optimizing the objective function. \n",
       "\n",
       "For example, for sentiment classifier we can use a logistic regression which learns a vector of weights and a bia term z=w*x+b $P(y=1)=\\sigma(w \\cdot x+b)=\\frac{1}{1+e^{-(w \\cdot x+b)}}$\n",
       "\n",
       "\n",
       "And we can make a decision using a arbitarty dicision boundry, 0.5 in this case $\\hat{y}=\\left\\{\\begin{array}{c}\n",
       "1 \\text { if } P(y=1 \\mid x)>0.5 \\\\\n",
       "0 \\text { otherwise }\n",
       "\\end{array}\\right.$\n",
       "\n",
       "\n",
       "To learn the weights and bias, we need 2 components: \n",
       "\n",
       "1. An objective function or loss function that tells us the distance between the system output and the gold output \n",
       "2. An algorithm like stochastic gradient descent to optimize the objective function and minimize the loss function, which is how much estimated y different from true y \n",
       "\n",
       "We can use mean squared error for example $L_{M S E}(\\hat{y}, y)=\\frac{1}{2}(\\hat{y}-y)^{2}$\n",
       "\n",
       "\n",
       "We can also use cross-entropy loss which is negative log likelihood loss$L_{C E}(\\hat{y}, y)=-[y \\log \\sigma(w \\cdot x+b)+(1-y) \\log (1-\\sigma(w \\cdot x+b))]$\n",
       "\n",
       "\n",
       "\n",
       "\n",
       "Gradient descent is a method to find a minimum of a function by figuring out in which direction the function's slope is rising the most deeply and moving in the opposite direction.\n",
       "\n",
       "Logistic regress's loss function is convex with just 1 minumim, so there is no local minimum. \n",
       "\n",
       "The magnitude of amount to move in gradient descent is called larning rate. Faster learning has higher learning rate. \n",
       "\n",
       "The loss for a batch of data or entire dataset is the average loss over m examples$\\operatorname{Cost}(w, b)=-\\frac{1}{m} \\sum_{i=1}^{m} y^{(i)} \\log \\sigma\\left(w \\cdot x^{(i)}+b\\right)+\\left(1-y^{(i)}\\right) \\log \\left(1-\\sigma\\left(w \\cdot x^{(i)}+b\\right)\\right)$\n",
       "\n",
       "\n",
       "The gradient for multiple data point is the sum of individual gradients$\\frac{\\partial \\operatorname{Cost}(w, b)}{\\partial w_{j}}=\\sum_{i=1}^{m}\\left[\\sigma\\left(w \\cdot x^{(i)}+b\\right)-y^{(i)}\\right] x_{j}^{(i)}$\n",
       "\n",
       "\n",
       "Stochastic GD chooses a single random example at a time and updates its weight on that example, but the update can fluctuate. \n",
       "An alternative is batch training which computes the gradient over the entire dataset. This method gives better estimate on which direct to move but takes long time to compute. \n",
       "So a commonly used compromise is mini-batch training.\n",
       "\n",
       "\n",
       "\n",
       "Overfitting will result poor generalization and performance on unseen test. In logistic regression, a feature only occur in one class will get a high weight, \n",
       "so we need to add regularization to loss function penalize large weights. L1 is Lasso and L2 is ridge. \n",
       "\n",
       "\n",
       "\n",
       "Apart from binary classifition we may want to classify into more than two classes, and we want to know the probability of each class. \n",
       "We will use a generalization of the sigmoid function called softmax to get proper probability which takes input of vector z and outputs a vector of values normalized into probabilities $\\operatorname{softmax}\\left(z_{i}\\right)=\\frac{e^{z_{j}}}{\\sum_{j=1}^{k} e^{z_{j}}} 1 \\leq i \\leq k$\n",
       "\n",
       "\n",
       "Instead of outputtomg z directly, logistic regression transforms it with sigmoid function which solve the problem that a small change in weights or bias can cause output to completely flip from 0 to 1$\\sigma(z)=\\frac{1}{1+e^{-z}}$\n",
       " where z=w·x+b \n",
       "\n",
       " This smoothness makes it easy to choose small change in weights and biases to achieve small change in the output. \n",
       "\n",
       " \n",
       "\n",
       "The simplest kind of NN is the feed forward NN which is a multilayer network that all units are fully connected with no cycles.\n",
       "Outputs from each layer are passed to the next layer and no output are passed back to lower layers. \n",
       "\n",
       "We represents parameter for the entire hidden layer by combining the wi and bi for each unit i into a single weight matrix W and a single bias vector b for the whole layer.\n",
       "\n",
       "Advantage of using a single matrix is that the hidden layer computation can be done with matrix operations \n",
       "\n",
       "1. multiply the weight matri by input vector x \n",
       "2. adding the bias vector b \n",
       "3. apply activation g: h = σ(Wx+b) \n",
       "\n",
       "Like the hidden layer, the output layer also has a weight matrix U. Its weight matrix is multiplied by input vector h to produce intermediate output z: z=Uh. \n",
       "\n",
       "\n",
       "\n",
       "The final equations for a feedforward network with a single hidden layer, which takes an input vector x, outputs a probability distribution y, and is parameterized by weights matrices W and U and a bias vector b: \n",
       "\n",
       "h = σ(Wx+b)\n",
       "\n",
       "z=Uh\n",
       "\n",
       "y=softmax(z)\n",
       "\n",
       "\n",
       "\n",
       "NN stacks layers relative to perceptrons. \n",
       "\n",
       "If we use liner activation function, the resulting nn will be a single layer nn \n",
       "\n",
       "To train neural nets, we need to learn the best paraments, so we need a loss function (cross-entropy loss), \n",
       "an optimization algorithm (gradient descent), and a way of computing the gradient of the loss function (error propagation). \n",
       "\n",
       "Backpropagation is invented for nn, but is related to general procedure called backward differentiation, which uses chain rule. \n",
       "It computes the gradient of loss function which requires looking back through all layers in the networkenables us to correctly update all layers in nn \n",
       "\n",
       "For f(x) = u(v(w(x))), the derivative of f(x) is $\\frac{d f}{d x}=\\frac{d u}{d v} \\cdot \\frac{d v}{d w} \\cdot \\frac{d w}{d x}$\n",
       "\n",
       "## Module 13 Definitions\n",
       "* **Concept** - definition\n",
       "\n",
       "\n",
       "# Module 14: Natural Language Processing\n",
       "## SLP Chapter 9.1 Language Models Revisited\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 9.2 Recurrent Neural Networks\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 9.3 RNNs as Language Models\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.1 Lexical Semantics\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.2 Vector Semantics\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.3 Words and Vectors\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.4 Cosine for measuring similarity\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.8 Word2vec\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.10 Semantic properties of embeddings\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.11 Bias and Embeddings\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.12 Evaluating Vector Models\n",
       " Your summary here \n",
       "\n",
       "## Module 14 Lecture Notes\n",
       "\n",
       "Neural LM associate each word in the vocabulary with a vector representation, creating a notion of similarity between words. \n",
       "Express the joint probability probability function of a word sequence in terms of the word vectors for the words in that sequence. \n",
       "simutaneously learn the word vectors and the parameters of the function.\n",
       "\n",
       "\n",
       "\n",
       "Neural language models is slower to train than n-gram, but have below advantages: \n",
       "\n",
       "1. does not need smoothing \n",
       "2. can handle longer histories, large N \n",
       "3. can generalize over contexts of similar words, for example, after see blue, gree, can score green car after observe blue car \n",
       "4. higher accuracy \n",
       "\n",
       "\n",
       "The input to NN is a k-gram of words w1:k.\n",
       "\n",
       "The output is a probability disctribution over the next word. \n",
       "\n",
       "k context words are treated as a word window and each word is associated with an embedding vector. \n",
       "\n",
       "Input vector x just concatenates v(w) for each of the k words.\n",
       "\n",
       "While training, the identities of the first k-1 words are used as features and the last word is used as target label for the classification. \n",
       "The model is trained using cross-entropy loss. \n",
       " \n",
       "We can construnct a table that store observed sequence to look up the probability of seeing a word given a history. \n",
       "\n",
       "When we have a new unseen sequence we can back-off, smoothing or interpolation. \n",
       "\n",
       "We can also generalizing like bedroom vs room. \n",
       "\n",
       "\n",
       "\n",
       "We also want to represent the mearning of a word like synonyms, antonyms, connotations, sematic roles, entailment. \n",
       "\n",
       "In vector space model each column vector represents a document, each row vector represents a term, \n",
       "and the value in a cell is based on how ofter that term occurred in that document. The length of the document vectors is the size of the vocabulary.\n",
       "Document vector will be sparsed and we can measure how similar two documents are by comparing their column vectors. \n",
       "\n",
       "\n",
       "\n",
       "In a term-term matrix, or a term-context matrix, the length of the vector is now |V| instead of number of documents. \n",
       "The value in a cell indicates how often A(row) in a context window surrounding by B (col). \n",
       "\n",
       "We can look at a window of +/- n words, or using more complex contexts like dependency patterns, subj-of-verb, adj-mod, obj-of-verb, etc. \n",
       "\n",
       "Raw word frequency is also not a great measure of association between words, because \"the\" and \"of\" will be very skewed. We want to measure whether a context word is informative about the target word, so we can use TF-IDF or PPMI. \n",
       "\n",
       "TF-IDF=term frequency (how oftern a word occurred in a document)*inverse document frequency (1/number of documents that if occurred in) \n",
       "\n",
       "We prefer dense vectors over sparse vectors, because its easy to use as features with fewer weights to tune, generalize bettern, and capture synonymy better. \n",
       "We can train a classifier to get that: \n",
       "\n",
       "1. Treat the target word and a neighboring context word as positive examples \n",
       "2. Randomly sample other words in the lexicon to get negative samples \n",
       "3. use logistic regression to train a classifier to distinguish these two cases \n",
       "4. use the weights as embeddings \n",
       "\n",
       "For example, Word2vec instead of counting how often each word w occurs near \"A\", it trains a classifier on a binary prediction to predict is w likely to show up near \"A\" through skip-gram algorithms: \n",
       "\n",
       "1. Treat the target word and a neighboring context word as positive examples. \n",
       "2. Randomly sample other words in the lexicon to get negative samples \n",
       "3. Use logistic regression to train a classifier to distinguish those two cases \n",
       "4. Use the weights as the embeddings \n",
       "\n",
       "\n",
       " \n",
       "\n",
       "## Module 14 Definitions\n",
       "* **Concept** - definition\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "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))"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "Copy of Template_for CIS521_midterm_2_notes.ipynb",
   "provenance": []
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
