solutions-04-part-01.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "# Connect Intensive - Machine Learning Nanodegree\n",
    "# Lesson 04: Natural Language Processing (NLP) Mini-Projects\n",
    "# Part 01: Bayes NLP Mini-Project\n",
    "\n",
    "## Objectives\n",
    "  - Understand how [Bayes Rule](https://en.wikipedia.org/wiki/Bayes%27_theorem) derives from [conditional probability](https://en.wikipedia.org/wiki/Conditional_probability)\n",
    "  - Write methods, utilizing Python dictionary objects and string methods such as `str.split()`.\n",
    "  - Apply Bayes Rule to simple NLP: missing word prediction problems\n",
    "  \n",
    "## Prerequisites\n",
    "  - Basic Python knowledge in strings and dictionaries would help."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bayes Rule\n",
    "Here is a brief description of Bayes rule -- if you're already familiar, feel free to skip ahead to the next section, **Bayes Rule in NLP**.\n",
    "\n",
    "Bayesian learning starts from an application of conditional probability. Suppose we have some **hypothesis** $h$ that occurs with probability $P(h)$. For example, in the field of oncology, we might be concerned about cancer rates. One hypothesis could be $h = $ \"The patient has cancer\". We may call the set of all possible hypotheses $H$, or the **hypothesis space**. If we have no other data about the patient, $P(h)$ is known as the **prior probability**, that is, prior to learning any data about the patient.\n",
    "\n",
    "Now suppose there's some diagnostic screening we can conduct for the specific type of cancer. The screen can come back positive or negative. We can represent this fact as the **training data** $D$ for the instance. For example, one possible training data could be $D = $ \"The diagnostic test for the patient is negative\". We can then write a **conditional probability** $P(h|D)$ (read as \"probability of hypothesis $h$ given training data $D$\"). For our example, this represents the probability that the patient has cancer, given that we know the diagnostic test for the patient is negative. Because we evaluate this probability *after* knowledge of the training data, this quantity is also known as the **posterior probability**.\n",
    "\n",
    "The probability of the **conjunction** $\\land$ of two events can be computed by conditional probabilities:\n",
    "$$P(D \\land h) = P(D|h)\\cdot P(h) = P(h|D)\\cdot P(D)$$\n",
    "Here, the quantity $P(D \\land h)$ represents the probability of the training data $D$ and the hypothesis $h$ **both** being true for our patient.\n",
    "\n",
    "The next term $P(D|h)\\cdot P(h)$ is the product of (1) the conditional probability of training data $D$ given the hypothesis $h$ is true, and (2) the prior probability of hypothesis $h$ being true. Here, we've conditioned on $h$ being true.\n",
    "\n",
    "The last term $P(h|D)\\cdot P(D)$ is the product of (1) the conditional (posterior) probability of hypothesis $h$ given the training data $D$ is true, and (2) the prior probability of the training data $D$ being true. Here, we've conditioned on $D$ being true.\n",
    "\n",
    "Bayes rule solves the above equation for the posterior probability $P(h|D)$:\n",
    "\n",
    "$$\\boxed{P(h|D) = \\dfrac{P(D|h)\\cdot P(h)}{P(D)}}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bayes Rule in NLP\n",
    "We are not going to be looking at a problem so grim as cancer diagnosis. Instead, we will apply Bayes rule to making predictions about words.\n",
    "\n",
    "Suppose we have the following quote (from the movie Office Space):\n",
    "> \"So if you could just go ahead and pack up your stuff and move it down there, that would be terrific, OK?\"\n",
    "\n",
    "Also suppose this text is the entire population of text we have to go from. We can ask a few questions based on this sentence:\n",
    "  1. What is the probability of finding the word \"you\" after the word \"if\"?\n",
    "  2. What is the probability that a randomly selected word from the sentence is \"you\"?\n",
    "  3. What is the probability that a randomly selected word from the sentence is \"if\"?\n",
    "  \n",
    "Enter your answers in the Bayes NLP Mini-Project \"Quiz: Calculations\"."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise: Maximum likelihood\n",
    "\n",
    "In this exercise, you will write a method, `NextWordProbability(sampletext,word)`, that creates a Python dictionary from a string `sampletext` and a target word `word`. The keys of the dictionary will be the words that follow the target word `word`, and the values will be the number of times the key follows the target word `word`. For example,  the output of the following code:\n",
    "```\n",
    "memo = \"If you could just go ahead and pack up your stuff and move it down there, that would be terrific, OK?\"\n",
    "word = \"and\"\n",
    "print(NextWordProbability(memo,word))\n",
    "```\n",
    "should be the dictionary:\n",
    "```\n",
    "{'move': 1, 'pack': 1}\n",
    "```\n",
    "Don't worry about removing punctuation or changing upper or lower case letters.\n",
    "\n",
    "**Complete** the method `NextWordProbability` in the cell below and then **run** the cell. You may want to use [the string method `split`](https://docs.python.org/2/library/stdtypes.html#string-methods), and refer to [the Python documentation on dictionaries](https://docs.python.org/2/library/stdtypes.html#mapping-types-dict).  Then, you can test your method by running the cell below it to try some test cases. When you feel confident your `NextWordProbability` method works, you can copy and paste the method into the Bayes NLP Mini-Project \"Quiz: Maximum Likelihood\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# When you are happy with your NextWordProbability method,\n",
    "# you may copy and paste it into the Bayes NLP Mini-Project\n",
    "# \"Quiz: Maximum Likelihood\"\n",
    "\n",
    "def NextWordProbability(sampletext,word):\n",
    "    words = sampletext.split()\n",
    "    prevword = None\n",
    "    d = {}\n",
    "    for w in words:\n",
    "        if prevword == word:\n",
    "            if w in d:\n",
    "                d[w] += 1\n",
    "            else:\n",
    "                d[w] = 1\n",
    "        prevword = w\n",
    "            \n",
    "    return d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'move': 1, 'pack': 1}\n",
      "{'to': 1, 'all': 1}\n",
      "{'tomorrow.': 1, 'on': 1}\n"
     ]
    }
   ],
   "source": [
    "# Test cases: see how well your NextWordProbability method works.\n",
    "\n",
    "memo1 = \"If you could just go ahead and pack up your stuff and move it down there, that would be terrific, OK?\"\n",
    "word1 = \"and\"\n",
    "print(NextWordProbability(memo1,word1))\n",
    "# Output should be:\n",
    "# {'move': 1, 'pack': 1}\n",
    "\n",
    "memo2 = \"Milt, we're gonna need to go ahead and move you downstairs into storage B. We have some new people coming in, and we need all the space we can get. So if you could just go ahead and pack up your stuff and move it down there, that would be terrific, OK?\"\n",
    "word2 = \"need\"\n",
    "print(NextWordProbability(memo2,word2))\n",
    "# Output should be:\n",
    "# {'to': 1, 'all': 1}\n",
    "\n",
    "memo3 = \"Hello Peter, what's happening? Ummm, I'm gonna need you to go ahead and come in tomorrow. So if you could be here around 9 that would be great, mmmk... oh oh! and I almost forgot ahh, I'm also gonna need you to go ahead and come in on Sunday too, kay. We ahh lost some people this week and ah, we sorta need to play catch up.\"\n",
    "word3 = \"in\"\n",
    "print(NextWordProbability(memo3,word3))\n",
    "# Output should be:\n",
    "# {'tomorrow.': 1, 'on': 1}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Conditioning multiple times\n",
    "Suppose we have used our `NextWordProbability` method to compute probabilities for the next word based on sample text, and now we are faced with a situation where we have two missing words in a row: \"for --- ---\", and we want to know the most likely candidate for the *second* missing word based on the following probabilities:\n",
    "\n",
    "$$\\begin{array}{rcl}\n",
    "P(\\text{ \"for this\" }|\\text{\"for ---\"})&=&0.4\\\\\n",
    "P(\\text{ \"for that\" }|\\text{\"for ---\"})&=&0.3\\\\\n",
    "P(\\text{ \"for those\" }|\\text{\"for ---\"})&=&0.3\\end{array}$$\n",
    "\n",
    "$$\\begin{array}{rclrcl}\n",
    "P(\\text{ \"this time\" }|\\text{\"this ---\"})&=&0.6\\quad&P(\\text{ \"this job\" }|\\text{\"this ---\"})&=&0.4\\\\\n",
    "P(\\text{ \"that job\" }|\\text{\"that ---\"})&=&0.8\\quad&P(\\text{ \"that time\" }|\\text{\"that ---\"})&=&0.2\\\\\n",
    "P(\\text{ \"those items\" }|\\text{\"those ---\"})&=&1.0\\end{array}$$\n",
    "\n",
    "Which word is the most likely candidate for the *second* missing word after \"for\"? ...with what probability?\n",
    "\n",
    "Enter your answers in the Bayes NLP Mini-Project \"Quiz: Optimal Classifier Example\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise: Bayes Optimal Classifier\n",
    "In this exercise, you will write a method `LaterWords(sample,word,distance)` that determines the most likely word to appear `distance` words after the target word `word` based on the text in the string `sample`. For example, a call to the method:\n",
    "```\n",
    "LaterWords(memo,\"and\",2)\n",
    "```\n",
    "would return a string: the most frequent word appearing 2 words after `\"and\"` in the string `memo`, *e.g.* \"and --- **---**\"\n",
    "\n",
    "**Complete** the procedure `LaterWords` in the cell below and then **run** the cell. You may want to call your method `NextWordProbability()`, and you may refer to [the Python documentation on dictionaries](https://docs.python.org/2/library/stdtypes.html#mapping-types-dict).  Then, you can test your method by running the cell below it to try some test cases. When you feel confident your `LaterWords` method works, you can copy and paste the method into the Bayes NLP Mini-Project \"Quiz: Optimal Classifier Exercise\".\n",
    "\n",
    "**Note:** If you choose to call `NextWordProbability()` within `LaterWords()`, you will also need to copy and paste your implementation of the `NextWordProbability()` method into the Bayes NLP Mini-Project \"Quiz: Optimal Classifier Exercise\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#------------------------------------------------------------------\n",
    "\n",
    "#\n",
    "#   Bayes Optimal Classifier\n",
    "#\n",
    "#   In this quiz we will compute the optimal label for a second missing word in a row\n",
    "#   based on the possible words that could be in the first blank\n",
    "#\n",
    "#   Finish the procedure, LaterWords(), below\n",
    "#\n",
    "#   You may want to use NextWordProbability(), depending on how you choose to approach this problem\n",
    "#\n",
    "\n",
    "def LaterWords(sample,word,distance):\n",
    "    '''@param sample: a sample of text to draw from\n",
    "    @param word: a word occuring before a corrupted sequence\n",
    "    @param distance: how many words later to estimate (i.e. 1 for the next word, 2 for the word after that)\n",
    "    @returns: a single word which is the most likely possibility\n",
    "    '''\n",
    "    # Initialize word_dict with the word parameter\n",
    "    word_dict = {word:1}\n",
    "    \n",
    "    # The module sys allows us to check the python version number\n",
    "    import sys\n",
    "    \n",
    "    # Implementations are slightly different for Python 2.7 and Python 3.x\n",
    "    if sys.version_info[0] == 2: # Python 2.7 implementation\n",
    "        for idx in range(distance):\n",
    "            # Create a new dictionary to conduct Naive Bayes\n",
    "            new_dict = {}\n",
    "            # Iterate over each word and word count in word_dict\n",
    "            for w, w_count in word_dict.iteritems():\n",
    "                # Naive Bayes -- probabilities (hence word counts) are multiplicative:\n",
    "                for new_word, new_count in NextWordProbability(sample,w).iteritems():\n",
    "                    # If the new_word is already in new_dict, add new_count weighted by w_count to the value:\n",
    "                    if new_word in new_dict:\n",
    "                        new_dict[new_word] += w_count * new_count\n",
    "                    # If the new_word is not yet in new_dict, initialize with new_count weighted by w_count:\n",
    "                    else:\n",
    "                        new_dict[new_word] = w_count * new_count\n",
    "            # Repeat process \"distance\" times, replacing word_dict with new_dict\n",
    "            word_dict = new_dict\n",
    "\n",
    "        # Return the word with the maximum value from Naive Bayes\n",
    "        return max(word_dict.iterkeys(), key=(lambda key: word_dict[key]))\n",
    "    \n",
    "    elif sys.version_info[0] == 3: # Python 3.x implementation\n",
    "        for idx in range(distance):\n",
    "            # Create a new dictionary to conduct Naive Bayes\n",
    "            new_dict = {}\n",
    "            # Iterate over each word and word count in word_dict\n",
    "            for w, w_count in word_dict.items():\n",
    "                # Naive Bayes -- probabilities (hence word counts) are multiplicative:\n",
    "                for new_word, new_count in NextWordProbability(sample,w).items():\n",
    "                    # If the new_word is already in new_dict, add new_count weighted by w_count to the value:\n",
    "                    if new_word in new_dict:\n",
    "                        new_dict[new_word] += w_count * new_count\n",
    "                    # If the new_word is not yet in new_dict, initialize with new_count weighted by w_count:\n",
    "                    else:\n",
    "                        new_dict[new_word] = w_count * new_count\n",
    "            # Repeat process \"distance\" times, replacing word_dict with new_dict\n",
    "            word_dict = new_dict\n",
    "\n",
    "        # Return the word with the maximum value from Naive Bayes\n",
    "        return max(word_dict.keys(), key=(lambda key: word_dict[key]))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "come\n",
      "on\n",
      "to\n"
     ]
    }
   ],
   "source": [
    "# Test cases: see how well your LaterWords procedure works.\n",
    "\n",
    "sample_memo = '''\n",
    "Milt, we're gonna need to go ahead and move you downstairs into storage B. We have some new people coming in, and we need all the space we can get. So if you could just go ahead and pack up your stuff and move it down there, that would be terrific, OK?\n",
    "Oh, and remember: next Friday... is Hawaiian shirt day. So, you know, if you want to, go ahead and wear a Hawaiian shirt and jeans.\n",
    "Oh, oh, and I almost forgot. Ahh, I'm also gonna need you to go ahead and come in on Sunday, too...\n",
    "Hello Peter, whats happening? Ummm, I'm gonna need you to go ahead and come in tomorrow. So if you could be here around 9 that would be great, mmmk... oh oh! and I almost forgot ahh, I'm also gonna need you to go ahead and come in on Sunday too, kay. We ahh lost some people this week and ah, we sorta need to play catch up.\n",
    "'''\n",
    "\n",
    "corrupted_memo = '''\n",
    "Yeah, I'm gonna --- you to go ahead --- --- complain about this. Oh, and if you could --- --- and sit at the kids' table, that'd be --- \n",
    "'''\n",
    "\n",
    "print(LaterWords(sample_memo,\"ahead\",2))\n",
    "# Output: come\n",
    "print(LaterWords(sample_memo,\"and\",3))\n",
    "# Output: on\n",
    "print(LaterWords(sample_memo,\"you\",1))\n",
    "# Output: to"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bayes NLP Reflection\n",
    "The last few quizzes in the Bayes NLP Mini-Project allow you to reflect on how Bayes Rule was applied here for simple word prediction tasks. You may enter your answers in the last four quizzes of the Bayes NLP Mini-Project in the Classroom\n",
    "  1. What set of words in a memo do you think could help predict what a missing word might be? What are some advantages and disadvantages of using more or fewer possible influences in prediction?\n",
    "  2. If you wanted to measure the joint probability distribution of a missing word, given its position relative to every other word in the document, how many probabilities would you need to measure? Say the document is $N$ words long.\n",
    "  3. Given the corpus of text we have from our boss, we might like to identify some things he often says, and use that knowledge to make better predictions. What are some statements you see arising multiple times?\n",
    "  4. Suppose we've identified the following patterns in our boss' speech:\n",
    "        - \"Gonna need [you] to go ahead and\"\n",
    "        - \"So if you could ... that would be [great, terrific], [ok, okay, mmmk]\"\n",
    "        - \"Oh, and I almost forgot\"\n",
    "\n",
    "     Trying to search all [regular expressions](https://docs.python.org/2/library/re.html) of length up to 9 with multiple optional parts is computationally infeasible. But if we have these hypotheses to begin with, we can make extremely accurate guesses. For example, fill in the blanks in the following sentence:\n",
    "       > \"Yeah, I'm gonna --- you to go --- --- not complain about this. Oh, and if you could --- ahead and sit at the kids' table, that'd be ---.\""
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}