03-NLP/POS.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#  Parts-of-Speech Tagging (POS)\n",
    "\n",
    "Part-of-speech refers to the category of words (Noun, Verb, Adjective...) in the language.  \n",
    "The part-of-speech (POS) tagging is the process of assigning a part-of-speech tag to each word in an input text.  Tagging is difficult because some words can represent more than one part of speech at different times. They are  **Ambiguous**. Let's look at the following example: \n",
    "\n",
    "- The whole team played **well**. [adverb]\n",
    "- You are doing **well** for yourself. [adjective]\n",
    "- **Well**, this assignment took me forever to complete. [interjection]\n",
    "- The **well** is dry. [noun]\n",
    "- Tears were beginning to **well** in her eyes. [verb]\n",
    "\n",
    "POS are useful because you can use them to make assumptions about semantics. This would be critically important in search queries. Identifying the proper noun, the organization, the stock symbol, or anything similar would greatly improve everything ranging from speech recognition to search. They're used for identifying\n",
    "named entities too.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Here](http://relearn.be/2015/training-common-sense/sources/software/pattern-2.6-critical-fork/docs/html/mbsp-tags.html) is an example 'tag-set' or Part of Speech designation describing the two or three letter tag and their meaning. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The goal\n",
    "A simple tagger can be built using the **probability** that a word belongs to a specific tag.  \n",
    "To find out the probabilities we can use an existing dataset of sentences (articles from the WSJ) whose words have been properly tagged. Unambiguous words will have a probability near 100% of belonging to a tag, while for  ambiguous words, it depends on how often they are used according to each tag."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Data Sources\n",
    "This notebook will use two tagged data sets collected from the **Wall Street Journal (WSJ)**:  \n",
    "- One data set (**WSJ-2_21.pos**) will be used for **training**.\n",
    "- The other (**WSJ-24.pos**) for **testing**. \n",
    "- The tagged training data has been preprocessed to form a **vocabulary** (**hmm_vocab.txt**).  \n",
    "The words in the vocabulary are words from the training set that were used two or more times.  \n",
    "The vocabulary is augmented with a set of 'unknown word tokens'. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A few items of the training corpus list: \n",
      "['In\\tIN\\n', 'an\\tDT\\n', 'Oct.\\tNNP\\n', '19\\tCD\\n', 'review\\tNN\\n']\n"
     ]
    }
   ],
   "source": [
    "# load in the training corpus\n",
    "with open(\"../datasets/WSJ_02-21.pos\", 'r') as f:\n",
    "    training_corpus = f.readlines()  # list\n",
    "\n",
    "print(\"A few items of the training corpus list: \")\n",
    "print(training_corpus[0:5])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "989860"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(training_corpus)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you can see, the **training_corpus** is a list with all words extracted from English articles, together with their POS tag.  \n",
    "Almost one million of them!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A sample of the testing corpus\n",
      "['The\\tDT\\n', 'economy\\tNN\\n', \"'s\\tPOS\\n\", 'temperature\\tNN\\n', 'will\\tMD\\n', 'be\\tVB\\n', 'taken\\tVBN\\n', 'from\\tIN\\n', 'several\\tJJ\\n', 'vantage\\tNN\\n']\n"
     ]
    }
   ],
   "source": [
    "# load in the test corpus\n",
    "with open(\"../datasets/WSJ_24.pos\", 'r') as f:\n",
    "    testing_corpus = f.readlines()  # list\n",
    "\n",
    "print(\"A sample of the testing corpus\")\n",
    "print(testing_corpus[0:10])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "34199"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(testing_corpus)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Testing Corpus is similar, just a subset of the Training one.  \n",
    "It will be used at the end for calculating the model's accuracy."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A few items of the vocabulary list\n",
      "['!', '#', '$', '%', '&', \"'\", \"''\", \"'40s\", \"'60s\", \"'70s\", \"'80s\", \"'86\", \"'90s\", \"'N\", \"'S\", \"'d\", \"'em\", \"'ll\", \"'m\", \"'n'\", \"'re\", \"'s\", \"'til\", \"'ve\", '(']\n",
      "\n",
      "A few items at the end of the vocabulary list\n",
      "['yields', 'you', 'young', 'younger', 'youngest', 'youngsters', 'your', 'yourself', 'youth', 'youthful', 'yuppie', 'yuppies', 'zero', 'zero-coupon', 'zeroing', 'zeros', 'zinc', 'zip', 'zombie', 'zone', 'zones', 'zoning', '{', '}', '']\n"
     ]
    }
   ],
   "source": [
    "# read the vocabulary data, split by each line of text, and save the list\n",
    "with open(\"../datasets/hmm_vocab.txt\", 'r') as f:\n",
    "    voc_l = f.read().split('\\n')  # list\n",
    "\n",
    "print(\"A few items of the vocabulary list\")\n",
    "print(voc_l[0:25])\n",
    "print()\n",
    "print(\"A few items at the end of the vocabulary list\")\n",
    "print(voc_l[-25:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "# vocab: dictionary that has the index of the corresponding words\n",
    "vocabulary = {} \n",
    "\n",
    "# Get the index of the corresponding words. \n",
    "for i, word in enumerate(sorted(voc_l)): \n",
    "    vocabulary[word] = i       \n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "23777"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(vocabulary)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The **vocabulary** is an indexed list of words; almost 24K of them.  \n",
    "The unique words have been extracted from the training corpus.  \n",
    "  \n",
    "The first 20 words:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Vocabulary dictionary: key is the word, value is a unique integer\n",
      ":0\n",
      "!:1\n",
      "#:2\n",
      "$:3\n",
      "%:4\n",
      "&:5\n",
      "':6\n",
      "'':7\n",
      "'40s:8\n",
      "'60s:9\n",
      "'70s:10\n",
      "'80s:11\n",
      "'86:12\n",
      "'90s:13\n",
      "'N:14\n",
      "'S:15\n",
      "'d:16\n",
      "'em:17\n",
      "'ll:18\n",
      "'m:19\n",
      "'n':20\n"
     ]
    }
   ],
   "source": [
    "print(\"Vocabulary dictionary: key is the word, value is a unique integer\")\n",
    "cnt = 0\n",
    "for k,v in vocabulary.items():\n",
    "    print(f\"{k}:{v}\")\n",
    "    cnt += 1\n",
    "    if cnt > 20:\n",
    "        break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Testing words\n",
    "The testing set (WSJ-24.pos) has also been preprocessed to remove the tags to form **test_words.txt**. This is read in to create `y`, our target for the accuracy measurement, later on."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "with open(\"../datasets/test.words\", 'r') as f:\n",
    "    y = f.readlines()  # list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "34199"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['The\\n', 'economy\\n', \"'s\\n\", 'temperature\\n', 'will\\n', 'be\\n', 'taken\\n', 'from\\n', 'several\\n', 'vantage\\n', 'points\\n', 'this\\n', 'week\\n', ',\\n', 'with\\n', 'readings\\n', 'on\\n', 'trade\\n', ',\\n', 'output\\n']\n"
     ]
    }
   ],
   "source": [
    "print(y[0:20])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Parts-of-speech tagging \n",
    "We will start with the simplest possible parts-of-speech tagger and we will build up to the state of the art. \n",
    "\n",
    "## Training\n",
    "\n",
    "In this section, we will find the words that are not ambiguous. \n",
    "- For example, the word `is` is a verb and it is not ambiguous. \n",
    "- In the `WSJ` corpus, $86$% of the token are unambiguous (meaning they have only one tag) \n",
    "- About $14\\%$ are ambiguous (meaning that they have more than one tag)\n",
    "Before we start predicting the tags of each word, we will need to compute a few dictionaries that will help to generate the tables. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Emission counts\n",
    "\n",
    "The first dictionary to  compute (and the one that will be used initially) is the `emissionCounts` dictionary. This dictionary will be used to compute:\n",
    "\n",
    "$$P(w_i|t_i)\\tag{1}$$\n",
    "\n",
    "In other words, we will use it to compute **the probability of a word given its tag**. \n",
    "\n",
    "In order  to compute this probability, we will create an `emissionCounts` dictionary where \n",
    "- The keys are `(tag, word)` \n",
    "- The values are the number of times that pair showed up in the training set. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Transition counts\n",
    "The second dictionary is the `transitionCounts` dictionary which computes the number of times each tag happened next to another tag. \n",
    "\n",
    "This dictionary will be used to compute: \n",
    "$$P(t_i |t_{i-1}) \\tag{2}$$\n",
    "\n",
    "This is the probability of a tag at position $i$ given the tag at position $i-1$.\n",
    "\n",
    "In order to compute it the  `transitionCounts` dictionary has: \n",
    "- the keys are `(prev_tag, tag)`\n",
    "- the values are the number of times those two tags appeared in that order. \n",
    "\n",
    "To calculate the transition probabilities, we actually only use the parts of speech tags from the\n",
    "training corpus. So to calculate the probability of a speech tag transitioning to another  one, we first have to count the occurrences of that tag combination in the corpus, which is N. The number of all tag pairs starting with the first tag is M, for this corpus at least. So N out of M tag sequences in the training corpus starts with the first parts of speech tag. In other words, that is the transition probability for the second tag following the first tag."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Tag counts\n",
    "\n",
    "The last dictionary we will compute is the `tagCounts` dictionary: \n",
    "- The key is the tag \n",
    "- The value is the number of times each tag appeared."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Create the helper dictionaries\n",
    "\n",
    "We use a helper function that takes in the `training_corpus` and returns the three dictionaries mentioned above `transitionCounts`, `emissionCounts`, and `tagCounts`. \n",
    "- `emissionCounts`: maps (tag, word) to the number of times it happened. \n",
    "- `transitionCounts`: maps (prev_tag, tag) to the number of times it has appeared. \n",
    "- `tagCounts`: maps (tag) to the number of times it has occured. \n",
    "\n",
    "Implementation note: This routine utilises *defaultdict*, which is a subclass of *dict*. \n",
    "- A standard Python dictionary throws a *KeyError* if you try to access an item with a key that is not currently in the dictionary. \n",
    "- In contrast, the *defaultdict* will create an item of the type of the argument, in this case an integer with the default value of 0. \n",
    "- See [defaultdict](https://docs.python.org/3.3/library/collections.html#defaultdict-objects)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A POS tagger will necessarily encounter words that are not in its datasets. \n",
    "- To improve accuracy, these words are further analyzed during preprocessing to extract available hints as to their appropriate tag. \n",
    "- For example, the suffix 'ize' is a hint that the word is a verb, as in 'final-ize' or 'character-ize'. \n",
    "- A set of unknown-tokens, such as '--unk-verb--' or '--unk-noun--' will replace the unknown words in both the training and test corpus and will appear in the emission, transmission and tag data structures."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "import string\n",
    "\n",
    "\n",
    "# Punctuation characters\n",
    "punct = set(string.punctuation)\n",
    "\n",
    "# Morphology rules used to assign unknown word tokens\n",
    "noun_suffix = [\"action\", \"age\", \"ance\", \"cy\", \"dom\", \"ee\", \"ence\", \"er\", \"hood\", \"ion\", \"ism\", \"ist\", \"ity\", \"ling\", \"ment\", \"ness\", \"or\", \"ry\", \"scape\", \"ship\", \"ty\"]\n",
    "verb_suffix = [\"ate\", \"ify\", \"ise\", \"ize\"]\n",
    "adj_suffix = [\"able\", \"ese\", \"ful\", \"i\", \"ian\", \"ible\", \"ic\", \"ish\", \"ive\", \"less\", \"ly\", \"ous\"]\n",
    "adv_suffix = [\"ward\", \"wards\", \"wise\"]\n",
    "\n",
    "\n",
    "\n",
    "def assign_unk(tok):\n",
    "    \"\"\"\n",
    "    Assign unknown word tokens\n",
    "    \"\"\"\n",
    "    # Digits\n",
    "    if any(char.isdigit() for char in tok):\n",
    "        return \"--unk_digit--\"\n",
    "\n",
    "    # Punctuation\n",
    "    elif any(char in punct for char in tok):\n",
    "        return \"--unk_punct--\"\n",
    "\n",
    "    # Upper-case\n",
    "    elif any(char.isupper() for char in tok):\n",
    "        return \"--unk_upper--\"\n",
    "\n",
    "    # Nouns\n",
    "    elif any(tok.endswith(suffix) for suffix in noun_suffix):\n",
    "        return \"--unk_noun--\"\n",
    "\n",
    "    # Verbs\n",
    "    elif any(tok.endswith(suffix) for suffix in verb_suffix):\n",
    "        return \"--unk_verb--\"\n",
    "\n",
    "    # Adjectives\n",
    "    elif any(tok.endswith(suffix) for suffix in adj_suffix):\n",
    "        return \"--unk_adj--\"\n",
    "\n",
    "    # Adverbs\n",
    "    elif any(tok.endswith(suffix) for suffix in adv_suffix):\n",
    "        return \"--unk_adv--\"\n",
    "\n",
    "    return \"--unk--\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Helper: substitues word not in the vocabulary with \"unknown\"\n",
    "def get_word_tag(line, vocab): \n",
    "    if not line.split():\n",
    "        word = \"--n--\"\n",
    "        tag = \"--s--\"\n",
    "        return word, tag\n",
    "    else:\n",
    "        word, tag = line.split()\n",
    "        if word not in vocab: \n",
    "            # Handle unknown words\n",
    "            word = assign_unk(word)\n",
    "        return word, tag\n",
    "    return None "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "def create_dictionaries(corpus, vocab):\n",
    "    \"\"\"\n",
    "    Input: \n",
    "        corpus: a corpus where each line has a word followed by its tag.\n",
    "        vocab: a dictionary where keys are words in vocabulary and value is an index\n",
    "    Output: \n",
    "        emission_counts: a dictionary where the keys are (tag, word) and the values are the counts\n",
    "        transition_counts: a dictionary where the keys are (prev_tag, tag) and the values are the counts\n",
    "        tag_counts: a dictionary where the keys are the tags and the values are the counts\n",
    "    \"\"\"\n",
    "    \n",
    "    # initialize the dictionaries using defaultdict\n",
    "    emission_counts = defaultdict(int)\n",
    "    transition_counts = defaultdict(int)\n",
    "    tag_counts = defaultdict(int)\n",
    "    \n",
    "    # Initialize \"prev_tag\" (previous tag) with the start state, denoted by '--s--'\n",
    "    prev_tag = '--s--' \n",
    "    \n",
    "    # use 'i' to track the line number in the corpus\n",
    "    i = 0 \n",
    "    \n",
    "    # Each item in the training corpus contains a word and its POS tag\n",
    "    # Go through each word and its tag in the training corpus\n",
    "    for word_tag in corpus:\n",
    "        \n",
    "        # Increment the word_tag count\n",
    "        i += 1\n",
    "        \n",
    "        # Every 50,000 words, print the word count, just to see the progress\n",
    "        if i % 50000 == 0:\n",
    "            print(f\"word count = {i}\")\n",
    "            \n",
    "        # get the word and tag using the get_word_tag helper function \n",
    "        word, tag = get_word_tag(word_tag, vocab) \n",
    "        \n",
    "        # Increment the transition count for the previous word and tag\n",
    "        transition_counts[(prev_tag, tag)] += 1\n",
    "        \n",
    "        # Increment the emission count for the tag and word\n",
    "        emission_counts[(tag, word)] += 1\n",
    "\n",
    "        # Increment the tag count\n",
    "        tag_counts[tag] += 1\n",
    "\n",
    "        # Set the previous tag to this tag (for the next iteration of the loop)\n",
    "        prev_tag = tag\n",
    "        \n",
    "        \n",
    "    return emission_counts, transition_counts, tag_counts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "word count = 50000\n",
      "word count = 100000\n",
      "word count = 150000\n",
      "word count = 200000\n",
      "word count = 250000\n",
      "word count = 300000\n",
      "word count = 350000\n",
      "word count = 400000\n",
      "word count = 450000\n",
      "word count = 500000\n",
      "word count = 550000\n",
      "word count = 600000\n",
      "word count = 650000\n",
      "word count = 700000\n",
      "word count = 750000\n",
      "word count = 800000\n",
      "word count = 850000\n",
      "word count = 900000\n",
      "word count = 950000\n"
     ]
    }
   ],
   "source": [
    "emissionCounts, transitionCounts, tagCounts = create_dictionaries(training_corpus, vocabulary)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of POS tags: 46\n",
      "View these POS tags\n",
      "['#', '$', \"''\", '(', ')', ',', '--s--', '.', ':', 'CC', 'CD', 'DT', 'EX', 'FW', 'IN', 'JJ', 'JJR', 'JJS', 'LS', 'MD', 'NN', 'NNP', 'NNPS', 'NNS', 'PDT', 'POS', 'PRP', 'PRP$', 'RB', 'RBR', 'RBS', 'RP', 'SYM', 'TO', 'UH', 'VB', 'VBD', 'VBG', 'VBN', 'VBP', 'VBZ', 'WDT', 'WP', 'WP$', 'WRB', '``']\n"
     ]
    }
   ],
   "source": [
    "# get all the POS states\n",
    "tags = sorted(tagCounts.keys())\n",
    "print(f\"Number of POS tags: {len(tags)}\")\n",
    "print(\"View these POS tags\")\n",
    "print(tags)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We got mapped a total of 46 POS tags which is great: every tag mentioned in the Penn Databank is here."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The 'tags' are the Parts-of-speech designations found in the training data. \n",
    "- \"NN\" is noun, singular, \n",
    "- 'NNS' is noun, plural. \n",
    "- In addition, there are helpful tags like '--s--' which indicate a start of a sentence.\n",
    "- You can get a more complete description at [Penn Treebank II tag set](https://www.clips.uantwerpen.be/pages/mbsp-tags). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "transition examples: \n",
      "(('--s--', 'IN'), 5050)\n",
      "(('IN', 'DT'), 32364)\n",
      "(('DT', 'NNP'), 9044)\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print(\"transition examples: \")\n",
    "for ex in list(transitionCounts.items())[:3]:\n",
    "    print(ex)\n",
    "print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The transition dictionary shows how often we go from a tag to another, for example from DT (a determiner, an article such as 'the', or 'a') to a NNP (proper noun) is 9044 times"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "emission examples: \n",
      "(('DT', 'any'), 721)\n",
      "(('NN', 'decrease'), 7)\n",
      "(('NN', 'insider-trading'), 5)\n",
      "\n",
      "ambiguous word example: \n",
      "('RB', 'back') 304\n",
      "('VB', 'back') 20\n",
      "('RP', 'back') 84\n",
      "('JJ', 'back') 25\n",
      "('NN', 'back') 29\n",
      "('VBP', 'back') 4\n"
     ]
    }
   ],
   "source": [
    "print(\"emission examples: \")\n",
    "for ex in list(emissionCounts.items())[200:203]:\n",
    "    print (ex)\n",
    "print()\n",
    "\n",
    "\n",
    "print(\"ambiguous word example: \")\n",
    "for tup,cnt in emissionCounts.items():\n",
    "    if tup[1] == 'back': print (tup, cnt) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "EmissionCounts dictionary is the most interesting: we can see that the word 'any' has been labelled as a DT (determiner) 721 times.  \n",
    "We can search all the tags used for a specific word (for example 'back') and see that most of the times was tagged as RB (adverb) but not always, it can be also a verb! It's ambiguous."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's parse some words and sentences example, using the new dictionaries.  \n",
    "We create two helper functions first:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "# we assume that we have the emission dictionary and the tags available\n",
    "\n",
    "def getWordPOS(word):\n",
    "    \"\"\"\n",
    "    Input: \n",
    "        word: the word to be tagged.\n",
    "    Output: \n",
    "        pos_final: the most probable tag for this word; --unknown-- if the word is not in the dictionaries\n",
    "    \"\"\"\n",
    "    count_final = 0\n",
    "    pos_final = ''\n",
    "        \n",
    "    for pos in tags:\n",
    "                        \n",
    "                # define the key as the tuple containing the POS and word\n",
    "        key = (pos,word)\n",
    "\n",
    "                # check if the (pos, word) key exists in the emissionCounts dictionary\n",
    "        if key in emissionCounts: # emissionCounts is global\n",
    "\n",
    "                # get the emission count of the (pos,word) tuple \n",
    "            count = emissionCounts[key]\n",
    "\n",
    "                    # keep track of the POS with the largest count\n",
    "            if count > count_final:\n",
    "\n",
    "                        # update the final count (largest count)\n",
    "                count_final = count\n",
    "\n",
    "                        # update the final POS\n",
    "                pos_final = pos\n",
    "                \n",
    "    if count_final == 0:\n",
    "        return \"- Unknown -\"\n",
    "    else:\n",
    "        return pos_final"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'NN'"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "getWordPOS('dog')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'NNS'"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "getWordPOS('dogs')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So dog is a singular noun (NN) and dogs is a plural noun (NNS).  \n",
    "So far so good.  \n",
    "Let's parse an entire sentence and we define another helper function for it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "def getSentencePOS(sentence):\n",
    "    \"\"\"\n",
    "    Input: \n",
    "        sentence: the sentence to be tagged. String.\n",
    "    Output: \n",
    "        a list of tuples: each word with its most probable tag\n",
    "    \"\"\"\n",
    "    words = sentence.split(\" \") # split into words (a list)\n",
    "    sentencePOS = [] # second list for the tags\n",
    "    \n",
    "    for word in words:\n",
    "        wordPOS = getWordPOS(word) # find the word's POS\n",
    "        sentencePOS.append(wordPOS)\n",
    "                \n",
    "            # return a list of tuples: (word, POS)\n",
    "    return list(zip(words, sentencePOS)) # combine the two lists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[('I', 'PRP'), ('have', 'VBP'), ('a', 'DT'), ('black', 'JJ'), ('cat', '- Unknown -')]\n"
     ]
    }
   ],
   "source": [
    "print(getSentencePOS(\"I have a black cat\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What?!        \n",
    "Cat is an unknow word? But dog could be identified?! This is racist..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[('I', 'PRP'), ('have', 'VBP'), ('not', 'RB'), ('a', 'DT'), ('big', 'JJ'), ('dog', 'NN')]\n"
     ]
    }
   ],
   "source": [
    "print(getSentencePOS(\"I have not a big dog\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ok, back to dogs.  \n",
    "Here you can see that 'I' is identified as a Pronoun (PRP), 'have' as a Verb conjugated (VBP) and 'big' is an adjective (JJ). Everything correct."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[('A', 'DT'), ('lion', 'NN'), ('is', 'VBZ'), ('always', 'RB'), ('faster', 'RBR'), ('than', 'IN'), ('the', 'DT'), ('turtle', 'NN')]\n"
     ]
    }
   ],
   "source": [
    "print(getSentencePOS(\"A lion is always faster than the turtle\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "'A' and 'The' are articles or determiners (DT), 'is' a verb 3rd person (VBZ), 'always' an adverb (RB) and 'faster' is a comparative (RBR). Still everything correct"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[('I', 'PRP'), ('eat', 'VB'), ('pizza', 'NN'), ('and', 'CC'), ('pasta', 'NN'), ('but', 'CC'), ('I', 'PRP'), ('do', 'VBP'), ('not', 'RB'), ('eat', 'VB'), ('meat', 'NN')]\n"
     ]
    }
   ],
   "source": [
    "print(getSentencePOS(\"I eat pizza and pasta but I do not eat meat\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here 'eat' is a Verb (VB) while 'and', 'but' are conjunctions (CC). Good"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[('I', 'PRP'), ('work', 'NN'), ('in', 'IN'), ('Shanghai', 'NNP')]\n"
     ]
    }
   ],
   "source": [
    "print(getSentencePOS(\"I work in Shanghai\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And here you can see that is failing: 'work' is not only a Noun, in this case is a Verb.  \n",
    "This is a case where the word is ambiguous and the parser is not enough sophisticated, as it just looks at the aboslute probabilities.  \n",
    "We will build a better one in the next notebook using the transition dictionary that gives an idea about the context of the word.  \n",
    "Stay tuned but now let's see how far this simple parser achieves on the testing dataset."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###  Testing\n",
    "\n",
    "Now we will test the accuracy of the parts-of-speech tagger using the `emissionCounts` dictionary. \n",
    "\n",
    "The testing set (WSJ-24.pos): \n",
    "- Contains both the test text and the true tag. \n",
    "- The testing set has also been preprocessed to remove the tags to form **test_words.txt**. \n",
    "- Now will be further processed to identify the end of sentences and handle words not in the vocabulary. \n",
    "- This forms the list `y_prepr`, the preprocessed text used to test our  POS taggers.\n",
    "\n",
    "Now:\n",
    "- Given a preprocessed test corpus `y_prepr`, we will assign a parts-of-speech tag to every word in that corpus. \n",
    "- Using the original tagged testing corpus, we will then compute what percent of the tags  got correct. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "orig = []\n",
    "y_prepr = []\n",
    "\n",
    "    # we already read the words from testing dataset into 'y'\n",
    "for cnt, word in enumerate(y):\n",
    "\n",
    "\n",
    "            # End of sentence\n",
    "    if not word.split():\n",
    "        orig.append(word.strip())\n",
    "        word = \"--n--\"\n",
    "        y_prepr.append(word)\n",
    "        continue\n",
    "\n",
    "            # Handle unknown words\n",
    "    elif word.strip() not in vocabulary:\n",
    "        orig.append(word.strip())\n",
    "        word = assign_unk(word)\n",
    "        y_prepr.append(word)\n",
    "        continue\n",
    "\n",
    "    else:\n",
    "        orig.append(word.strip())\n",
    "        y_prepr.append(word.strip())\n",
    "\n",
    "assert(len(orig) == len(y)) # just to be sure\n",
    "assert(len(y_prepr) == len(y))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The length of the preprocessed testing corpus:  34199\n",
      "This is a sample of the testing corpus: \n",
      "['The', 'economy', \"'s\", 'temperature', 'will', 'be', 'taken', 'from', 'several', '--unk--', 'points', 'this', 'week', ',', 'with', 'readings', 'on', 'trade', ',', 'output']\n"
     ]
    }
   ],
   "source": [
    "#corpus without tags, preprocessed\n",
    "\n",
    "print('The length of the preprocessed testing corpus: ', len(y_prepr))\n",
    "print('This is a sample of the testing corpus: ')\n",
    "print(y_prepr[0:20])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Prediction\n",
    "\n",
    "Let's compute the accuracy of the model:\n",
    "\n",
    "- assign a part of speech to a word (the most frequent POS for that word in the training set). \n",
    "- then evaluate how well this approach works.  Each time we predict based on the most frequent POS for the given word, we check whether the actual POS of that word is the same.  If so, the prediction was correct!\n",
    "- calculate the accuracy as the number of correct predictions divided by the total number of words for which we  predicted the POS tag."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Initialize the number of correct predictions to zero\n",
    "num_correct = 0\n",
    "\n",
    "# Get the (tag, word) tuples, stored as a set\n",
    "all_words = set(emissionCounts.keys())\n",
    "\n",
    "# Get the number of (word, POS) tuples in the corpus 'y'\n",
    "total = len(testing_corpus)\n",
    "\n",
    "for word, y_tup in zip(y_prepr, testing_corpus):\n",
    "    # Split the (word, POS) string into a list of two items\n",
    "    y_tup_l = y_tup.split()\n",
    "    \n",
    "    # Verify that y_tup contain both word and POS\n",
    "    if len(y_tup_l) == 2:\n",
    "        \n",
    "        # Set the true POS label for this word\n",
    "        true_label = y_tup_l[1]\n",
    "    else:\n",
    "        # If the y_tup didn't contain word and POS, go to next word\n",
    "        continue\n",
    "        \n",
    "    count_final = 0\n",
    "    pos_final = ''\n",
    "    \n",
    "    if word in vocabulary:\n",
    "        for pos in tags:\n",
    "            \n",
    "            # define the key as the tuple containing the POS and word\n",
    "            key = (pos,word)\n",
    "            \n",
    "            # check if the (pos, word) key exists in the emissionCounts dictionary\n",
    "            if key in emissionCounts: \n",
    "                # get the emission count of the (pos,word) tuple\n",
    "                count = emissionCounts[key]\n",
    "                \n",
    "                # keep track of the POS with the largest count\n",
    "                if count > count_final:\n",
    "                    # update the final count (largest count)\n",
    "                    count_final = count\n",
    "                    \n",
    "                    # update the final POS\n",
    "                    pos_final = pos\n",
    "                    \n",
    "        # If the final POS (with the largest count) matches the true POS:\n",
    "        if pos_final == true_label:\n",
    "            # Update the number of correct predictions\n",
    "            num_correct += 1\n",
    "            \n",
    "accuracy = num_correct / total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Accuracy of prediction using predict_pos is 0.8889\n"
     ]
    }
   ],
   "source": [
    "print(f\"Accuracy of prediction using predict_pos is {accuracy:.4f}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "88.9% is really good for this warm up exercise. With hidden markov models, we should be able to get **95% accuracy.**"
   ]
  }
 ],
 "metadata": {
  "coursera": {
   "schema_names": [
    "NLPC2-2"
   ]
  },
  "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.7.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}