03-NLP/POS2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#  Parts-of-Speech Tagging (POS)\n",
    "\n",
    "In [the first part](https://github.com/Mashimo/datascience/blob/master/03-NLP/POS.ipynb) we have seen how to build a simple tagger using the **probability** that a word belongs to a specific tag.  \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.   \n",
    "Tagging is difficult because some words can represent more than one part of speech at different times. They are  **Ambiguous**. We have seen that a simple tagger based on occurence probabilities reached a good accuracy but failed at correctly tagging a sentence like \"I work in Shanghai\" because it tagged work as a noun and not - in this case - as a verb.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The goal\n",
    "\n",
    "We will use now a different approach based on the Viterbi algorithm and the hidden markov model, that hopefully will improve the tagging accuracy.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Data Sources\n",
    "This notebook will use the same tagged data sets used when building the first tagger, 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'. \n",
    "  \n",
    "They are the same as the previous notebook, and pre-processing them is also the same so I will be faster here. Please refer to the first part for more details.\n",
    "  \n",
    "### Training data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "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": "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!\n",
    "  \n",
    "### Testing data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "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 testing 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": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "34199"
      ]
     },
     "execution_count": 3,
     "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": "markdown",
   "metadata": {},
   "source": [
    "### Testing words and vocabulary\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`, a helper list for the algorithm later on."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "with open(\"../datasets/test.words\", 'r') as f:\n",
    "    testing_words = f.readlines()  # list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "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(testing_words[0:20])"
   ]
  },
  {
   "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.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "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"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "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",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "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": [
    "print(\"A few items at the end of the vocabulary list\")\n",
    "print(voc_l[-25:])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "## Create the helper dictionaries\n",
    "\n",
    "Before we start predicting the tags of each word, we will need to compute - from the training corpus - a few dictionaries that will help to generate the tables.  \n",
    "Again, this is the same as done in the first part, so I will go quickly through them.\n",
    "- the `emissionCounts` dictionary will be used to compute **the probability of a word given its tag**.\n",
    "- the `transitionCounts` dictionary which computes the number of times each tag happened next to another tag. \n",
    "- the `tagCounts` dictionary computes the number of times each tag appeared."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "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": 10,
   "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": 11,
   "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",
    "            \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": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "emissionCounts, transitionCounts, tagCounts = create_dictionaries(training_corpus, vocabulary)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "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": "markdown",
   "metadata": {},
   "source": [
    "We didn't use the transition dictionary in the first model but we will be now."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "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": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "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(\"ambiguous word example: \")\n",
    "for tup,cnt in emissionCounts.items():\n",
    "    if tup[1] == 'back': print (tup, cnt) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can search all the tags used for a specific word (for example 'back') in the EmissionCounts dictionary 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": [
    "# Markov Models for POS\n",
    "\n",
    "Now we will build something more context specific. Concretely, we will be implementing a Hidden Markov Model (HMM) with a Viterbi decoder.  \n",
    "The HMM is one of the most commonly used algorithms in Natural Language Processing, and is a foundation to many deep learning techniques.  \n",
    "In addition to parts-of-speech tagging, HMM is used in speech recognition, speech synthesis, etc. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A [Markov chain](https://en.wikipedia.org/wiki/Markov_chain) is basically a directed graph: a data structure consisting of a set of objects (called nodes, the circles in the image); in our case they are the PoS tags of our model  that are connected together  by edges (the uni-directional lines in the image).  \n",
    "The arrows from state q1 to q2 represents the transition probability to move from q1 to q2.  \n",
    "  \n",
    "  The probability of the next event **only depends on the current events**.\n",
    "  \n",
    "![a super simple graph](pos8.png \"A Markov chain\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An [example of a Markov chain](https://setosa.io/ev/markov-chains/) could be a graph predicting if a day is sunny (S) or rainy (R), i.e. it has only two states. When the Markov chain is in state \"R\", it has a 0.9 probability of staying there (means the next day will also rain) and a 0.1 chance of leaving for the \"S\" state (means the next day will instead be sunny).   Likewise, \"S\" state has 0.9 probability of staying sunny and a 0.1 chance of transitioning to the \"R\" state.  \n",
    "  \n",
    "![a super simple example](pos7.png \"Weather example\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "  \n",
    "A sentence is a sequence of words with associated parts of speech tags.  \n",
    "We can represent that sequence with a graph where the parts of speech tags (NN, VB, O) are events that can occur depicted by the nodes of the model graph. The weights on the arrows between the states define the probability of going from one tag to another:  \n",
    "\n",
    "![a super simple graph for POS](pos9.png \"A Markov chain for POS\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#  Hidden Markov Models for POS\n",
    "\n",
    "The [Hidden Markov Model (HMM)](https://en.wikipedia.org/wiki/Hidden_Markov_model) is a statistical model in which the system being modeled is yes a Markov process – call it X – but with **unobservable (\"hidden\") states**.  \n",
    "The goal is to learn about X by observing another process Y whose behavior \"depends\" on X. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's see how the weather example above can have unobservable events.  \n",
    "Consider two friends, Alice and Bob, who live far apart from each other and who talk together daily over the telephone about what they did that day. Bob is only interested in three activities: *walking in the park*, *shopping* and *cleaning his apartment*.  \n",
    "The choice of what to do **is determined exclusively by the weather** on a given day.  \n",
    "Alice has no definite information about the weather but she knows general trends. Based on what Bob tells her he did each day, Alice **tries to guess what the weather must have been like.**\n",
    "\n",
    "Alice believes that the weather operates as a discrete Markov chain.  \n",
    "There are two states: \"Rainy\" and \"Sunny\", but she cannot observe them directly as they are \"hidden\" from her.  On each day, there is a certain chance that Bob will perform one of the following activities, depending on the weather: \"walk\", \"shop\", or \"clean\".  \n",
    "Since Bob tells Alice about his activities, those are the observations. The entire system is that of a hidden Markov model (HMM)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It's the same when we are trying to tag the POS on a sentence: we cannot observe the POS of each word but we can know the transition probabilities of another model trained on a given dataset."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Describe Markov models with matrixes\n",
    "The Markov model graph can be represented as a matrix with dimension n+1 by n, where n is the number of tags:\n",
    "- each element a(i,j) represents the probability to transition from tag *i* to tag *j*\n",
    "- when no previous state, we introduce an initial state π.\n",
    "- The sum of all transition from a state should always be 1.\n",
    "  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To describe a HMM you will need **a transition matrix A** (for example with the probabilities of rainy and sunny states) and also **an emission matrix B**.  \n",
    "The second matrix contains the probabilities of the observable states based on the unobservable: how likely Bob is to perform a certain activity on each day. If it is rainy, there is a 50% chance that he is cleaning his apartment; if it is sunny, there is a 60% chance that he is outside for a walk."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For POS tagging, the hidden Markov model have emission probabilities matrix B describe the transition from the hidden states to the observables (the words of your corpus)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##  Generating Matrices\n",
    "\n",
    "Starting from the `emissionCounts`, `transitionCounts` and `tagCounts`, we will now implement the Hidden Markov Model. \n",
    "\n",
    "This will allow to quickly construct the \n",
    "- `A` transition probabilities matrix.\n",
    "- `B` emission probabilities matrix. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Transition matrix A\n",
    "\n",
    "To avoid division by zero since lot of entries in the transition matrix are zero, we apply smoothing to the probability formula.    \n",
    "The matrix A is computed with smoothing as follows: \n",
    "\n",
    "$$ P(t_i | t_{i-1}) = \\frac{C(t_{i-1}, t_{i}) + \\alpha }{C(t_{i-1}) +\\alpha * N}\\tag{1}$$\n",
    "\n",
    "- $N$ is the total number of tags\n",
    "- $C(t_{i-1}, t_{i})$ is the count of the tuple (previous POS, current POS) in `transition_counts` dictionary.\n",
    "- $C(t_{i-1})$ is the count of the previous POS in the `tag_counts` dictionary.\n",
    "- $\\alpha$ is a smoothing parameter.\n",
    "  \n",
    "\n",
    "The function below implements the `create_transition_matrix` for all tags. It outputs a matrix that computes the above equation (1) for each cell in matrix `A`.  \n",
    "Inputs are the transitionCounts and the tagCounts. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "def create_transition_matrix(alpha, tag_counts, transition_counts):\n",
    "    ''' \n",
    "    Input: \n",
    "        alpha: number used for smoothing\n",
    "        tag_counts: a dictionary mapping each tag to its respective count\n",
    "        transition_counts: transition count for the previous word and tag\n",
    "    Output:\n",
    "        A: matrix of dimension (num_tags,num_tags)\n",
    "    '''\n",
    "    # Get a sorted list of unique POS tags; e.g. all_tags[20]is 'NN'\n",
    "    all_tags = sorted(tag_counts.keys())\n",
    "    \n",
    "    # Get the number of unique POS tags, this will be n, the matrix size\n",
    "    num_tags = len(all_tags)\n",
    "    \n",
    "    # Initialize the transition matrix 'A' (size is n by n) to zero\n",
    "    A = np.zeros((num_tags, num_tags))\n",
    "    \n",
    "    # Get the unique transition tuples (previous POS, current POS)\n",
    "    trans_keys = set(transition_counts.keys())\n",
    "    \n",
    "    \n",
    "    # Go through each row of the transition matrix A\n",
    "    for i in range(num_tags):\n",
    "        \n",
    "        # Go through each column of the transition matrix A\n",
    "        for j in range(num_tags):\n",
    "\n",
    "            # Initialize the count of the (prev POS, current POS) to zero\n",
    "            count = 0\n",
    "        \n",
    "            # Define the tuple (prev POS, current POS)\n",
    "            # Get the tag at position i and tag at position j (from the all_tags list)\n",
    "            key = (all_tags[i], all_tags[j]) # this is a tuple (tag1, tag2)\n",
    "\n",
    "            # Check if the (prev POS, current POS) tuple \n",
    "            # exists in the transition counts dictionaory\n",
    "            if key in transition_counts:\n",
    "                \n",
    "                # If yes, get count from the transition_counts dictionary \n",
    "                # for the (prev POS, current POS) tuple\n",
    "                # we know that the transition dictionary contains key=tuple(pos1,pos2) and value=probability\n",
    "                # e.g. (('DT', 'NNP'), 9044)\n",
    "                count = transition_counts[key]\n",
    "                \n",
    "            # Get the count of the previous tag (index position i), how may times appeared in corpus\n",
    "            count_prev_tag = tag_counts[all_tags[i]]\n",
    "            \n",
    "            # Formula (1)\n",
    "            # Apply smoothing using count of the tuple, alpha, \n",
    "            # count of previous tag, alpha, and number of total tags\n",
    "            A[i,j] = (count + alpha) / (count_prev_tag + alpha * num_tags)\n",
    "\n",
    "    \n",
    "    return A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A subset of transition matrix A:\n",
      "              RBS            RP           SYM        TO            UH\n",
      "RBS  2.217069e-06  2.217069e-06  2.217069e-06  0.008870  2.217069e-06\n",
      "RP   3.756509e-07  7.516775e-04  3.756509e-07  0.051089  3.756509e-07\n",
      "SYM  1.722772e-05  1.722772e-05  1.722772e-05  0.000017  1.722772e-05\n",
      "TO   4.477336e-05  4.472863e-08  4.472863e-08  0.000090  4.477336e-05\n",
      "UH   1.030439e-05  1.030439e-05  1.030439e-05  0.061837  3.092348e-02\n"
     ]
    }
   ],
   "source": [
    "import pandas as pd\n",
    "\n",
    "\n",
    "alpha = 0.001\n",
    "\n",
    "\n",
    "A = create_transition_matrix(alpha, tagCounts, transitionCounts)\n",
    "\n",
    "print(\"A subset of transition matrix A:\")\n",
    "print(pd.DataFrame(A[30:35,30:35], index=tags[30:35], columns = tags[30:35] ))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That is an example of what the `A` transition matrix would look like (it is simplified to 5 tags for viewing. It is 46x46 in reality).\n",
    "\n",
    "Each cell gives the probability to go from one part of speech to another. \n",
    "- In other words, there is a 4.47e-8 chance of going from parts-of-speech `TO` to `RP`. \n",
    "- The sum of each row has to be equal to 1, because we assume that the next POS tag must be one of the available columns in the table."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###  The emission probabilities matrix B\n",
    "\n",
    "Now we will create the `B` transition matrix which computes the emission probability by counting the co-occurrences of a part of speech tag with a specific word.\n",
    "\n",
    "\n",
    "We will use smoothing as defined below: \n",
    "\n",
    "$$P(w_i | t_i) = \\frac{C(t_i, word_i)+ \\alpha}{C(t_{i}) +\\alpha * N}\\tag{2}$$\n",
    "\n",
    "- $C(t_i, word_i)$ is the number of times $word_i$ was associated with $tag_i$ in the training data (stored in `emission_counts` dictionary).\n",
    "- $C(t_i)$ is the number of times $tag_i$ was in the training data (stored in `tag_counts` dictionary).\n",
    "- $N$ is the number of words in the vocabulary\n",
    "- $\\alpha$ is a smoothing parameter. \n",
    "\n",
    "The matrix `B` is of dimension (num_tags, N), where num_tags is the number of possible parts-of-speech tags. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally the function below implements the `create_emission_matrix`  that computes the `B` emission probabilities matrix. The function takes in $\\alpha$, the smoothing parameter, `tagCounts`, which is the dictionary mapping each tag to its respective count and - this time - the `emissionCounts` dictionary where the keys are (tag, word) and the values are the counts. It outputs a matrix that computes equation (2) above for each cell in matrix `B`. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "def create_emission_matrix(alpha, tag_counts, emission_counts, vocab):\n",
    "    '''\n",
    "    Input: \n",
    "        alpha: tuning parameter used in smoothing \n",
    "        tag_counts: a dictionary mapping each tag to its respective count\n",
    "        emission_counts: a dictionary where the keys are (tag, word) and the values are the counts\n",
    "        vocab: a dictionary where keys are words in vocabulary and value is an index\n",
    "    Output:\n",
    "        B: a matrix of dimension (num_tags, len(vocab))\n",
    "    '''\n",
    "    \n",
    "    # get the number of POS tag\n",
    "    num_tags = len(tag_counts) # this is the number of rows of the B matrix\n",
    "    \n",
    "    # Get a list of all POS tags\n",
    "    all_tags = sorted(tag_counts.keys())\n",
    "    \n",
    "    # Get the total number of unique words in the vocabulary\n",
    "    num_words = len(vocab) # this is the number of columns of the B matrix\n",
    "    \n",
    "    # Initialize the emission matrix B with places for\n",
    "    # tags in the rows and words in the columns\n",
    "    B = np.zeros((num_tags, num_words)) \n",
    "    \n",
    "    # Get a set of all (POS, word) tuples \n",
    "    # from the keys of the emission_counts dictionary\n",
    "    # e.g. ('NN', 'dog')\n",
    "    emis_keys = set(list(emission_counts.keys()))\n",
    "        \n",
    "    # Go through each row (POS tags)\n",
    "    for i in range(num_tags):\n",
    "        \n",
    "        # Go through each column (words)\n",
    "        for j in range(num_words):\n",
    "\n",
    "            # Initialize the emission count for the (POS tag, word) to zero\n",
    "            count = 0\n",
    "                    \n",
    "            # Define the (POS tag, word) tuple for this row and column\n",
    "            key = (all_tags[i], vocab[j]) # this is a tuple (tag, word) as ('NN', 'dog')\n",
    "            \n",
    "            # check if the (POS tag, word) tuple exists as a key in emission counts\n",
    "            if key in emission_counts.keys():\n",
    "        \n",
    "                # Get the count of (POS tag, word) from the emission_counts\n",
    "                # we know that the emission dictionary contains key=tuple(pos,word) and value=count\n",
    "                # e.g. ('NN','dog') = 10 (appears ten times in corpus)\n",
    "                count = emission_counts[key]\n",
    "                \n",
    "            # Get the count of the POS tag (how may times appeared in corpus)\n",
    "            count_tag = tag_counts[all_tags[i]]\n",
    "                \n",
    "            # Apply smoothing and store the smoothed value \n",
    "            # into the emission matrix B for this row and column\n",
    "            B[i,j] = (count + alpha) / (count_tag+ alpha*num_words)\n",
    "\n",
    "    return B"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "# creating the emission probability matrix. this takes a few minutes to run. \n",
    "\n",
    "B = create_emission_matrix(alpha, tagCounts, emissionCounts, list(vocabulary))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "              725          well           dog          dogs          work\n",
      "CD   8.201296e-05  2.732854e-08  2.732854e-08  2.732854e-08  2.732854e-08\n",
      "NN   7.521128e-09  6.769767e-05  7.521880e-05  7.521128e-09  2.015670e-03\n",
      "NNS  1.670013e-08  1.670013e-08  1.670013e-08  1.169176e-04  1.670013e-08\n",
      "VB   3.779036e-08  3.779036e-08  3.779036e-08  3.779036e-08  4.345929e-03\n",
      "RB   3.226454e-08  1.319623e-02  3.226454e-08  3.226454e-08  3.226454e-08\n",
      "RP   3.723317e-07  3.723317e-07  3.723317e-07  3.723317e-07  3.723317e-07\n"
     ]
    }
   ],
   "source": [
    "# Try viewing emissions for a few words in a sample dataframe\n",
    "cidx  = ['725','well','dog', 'dogs', 'work']\n",
    "\n",
    "# Get the integer ID for each word\n",
    "cols = [vocabulary[a] for a in cidx]\n",
    "\n",
    "# Choose POS tags to show in a sample dataframe\n",
    "rvals =['CD','NN','NNS', 'VB','RB','RP']\n",
    "\n",
    "# For each POS tag, get the row number from the 'states' list\n",
    "rows = [tags.index(a) for a in rvals]\n",
    "\n",
    "# Get the emissions for the sample of words, and the sample of POS tags\n",
    "print(pd.DataFrame(B[np.ix_(rows,cols)], index=rvals, columns = cidx ))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That is an example of the matrix, only a subset of tags and words are shown.\n",
    "\n",
    "E.g. the probability for the tuple (NN, dog) is 7.5e-05, much higher than for (NNS, dog).\n",
    "\n",
    "But note that 'work' has similar probabilities to be a singular noun (NN) or a verb (VB)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Pre-process the corpus\n",
    "Finally, the corpus needs to be pre-processed (as in the first part) to tag the unknown words and mark the end of sentence:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "def preprocessCorpus(y):\n",
    "    \n",
    "    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))\n",
    "    \n",
    "    return y_prepr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "tw_prepr = preprocessCorpus(testing_words)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The length of the preprocessed test corpus:  34199\n",
      "This is a sample of the test_corpus: \n",
      "['The', 'economy', \"'s\", 'temperature', 'will', 'be', 'taken', 'from', 'several', '--unk--', 'points', 'this', 'week', ',', 'with', 'readings', 'on', 'trade', ',', 'output']\n"
     ]
    }
   ],
   "source": [
    "print('The length of the preprocessed test corpus: ', len(tw_prepr))\n",
    "print('This is a sample of the test_corpus: ')\n",
    "print(tw_prepr[0:20])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Viterbi Algorithm\n",
    "\n",
    "The Viterbi algorithm is a graph algorithm to find the most likely sequence of hidden states (or parts of speech tags in our case) — called the Viterbi path — that have the highest *a posteriori* probability for a sequence of observed events.\n",
    "\n",
    "The Viterbi algorithm is named after Andrew Viterbi, who proposed it in 1967 as a decoding algorithm for convolutional codes over noisy digital communication links.  \n",
    "It was introduced to Natural Language Processing as a method of part-of-speech tagging as early as 1987.\n",
    "  \n",
    "I cannot make a better explanation than what is [on Wikipedia](https://en.wikipedia.org/wiki/Viterbi_algorithm), completed with pseudocode and example in Python.  \n",
    "Now we will implement the Viterbi algorithm which makes use of dynamic programming. Specifically, we will use the two matrices `A` and `B` to compute the Viterbi algorithm in three main steps:  \n",
    "\n",
    "* **Initialization** - initialize the `best_paths` and `best_probabilities` matrices that we will be populating in `feed_forward`.\n",
    "* **Feed forward** - At each step,  calculate the probability of each path happening and the best paths up to that point. \n",
    "* **Feed backward**: This allows to find the best path with the highest probabilities. \n",
    "\n",
    "##  Initialization \n",
    "\n",
    "Let's start by initializing two matrices of the same dimension. \n",
    "\n",
    "- best_probs: Each cell contains the probability of going from one POS tag to a word in the corpus.\n",
    "(The initialization of matrix C tell the probability of every word belongs to a certain part of speech)\n",
    "\n",
    "- best_paths: A matrix that helps you trace through the best possible path in the corpus. \n",
    "(in D matrix, we store the labels that represent the different states we are traversing when finding the most likely sequence of parts of speech tags for the given sequence of words W1 all the way to Wk)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is how to initialize `best_probs`:\n",
    "- The probability of the best path going from the start index to a given POS tag indexed by integer $i$ is denoted by $\\textrm{best_probs}[s_{idx}, i]$.\n",
    "- This is estimated as the probability that the start tag transitions to the POS denoted by index $i$: $\\mathbf{A}[s_{idx}, i]$ AND that the POS tag denoted by $i$ emits the first word of the given corpus, which is $\\mathbf{B}[i, vocab[corpus[0]]]$.\n",
    "- Note that vocab[corpus[0]] refers to the first word of the corpus (the word at position 0 of the corpus). \n",
    "- **vocab** is a dictionary that returns the unique integer that refers to that particular word.\n",
    "\n",
    "Conceptually, it looks like this:\n",
    "$\\textrm{best_probs}[s_{idx}, i] = \\mathbf{A}[s_{idx}, i] \\times \\mathbf{B}[i, corpus[0] ]$\n",
    "\n",
    "\n",
    "In order to avoid multiplying and storing small values on the computer, we'll take the log of the product, which becomes the sum of two logs:\n",
    "\n",
    "$best\\_probs[i,0] = log(A[s_{idx}, i]) + log(B[i, vocab[corpus[0]]$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "def initialize(states, tag_counts, A, B, corpus, vocab):\n",
    "    '''\n",
    "    Scope: initializes the `best_probs` and the `best_paths` matrix\n",
    "    \n",
    "    Input: \n",
    "        states: a list of all possible parts-of-speech\n",
    "        tag_counts: a dictionary mapping each tag to its respective count\n",
    "        A: Transition Matrix of dimension (num_tags, num_tags)\n",
    "        B: Emission Matrix of dimension (num_tags, len(vocab))\n",
    "        corpus: a sequence of words whose POS is to be identified in a list \n",
    "        vocab: a dictionary where keys are words in vocabulary and value is an index\n",
    "    Output:\n",
    "        best_probs: matrix of dimension (num_tags, len(corpus)) of floats\n",
    "        best_paths: matrix of dimension (num_tags, len(corpus)) of integers\n",
    "    '''\n",
    "      # Get the total number of unique POS tags\n",
    "    num_tags = len(tag_counts)\n",
    "    \n",
    "      # Initialize best_probs matrix to zero\n",
    "      # POS tags as the rows, number of words in the corpus as the columns\n",
    "    best_probs = np.zeros((num_tags, len(corpus)))\n",
    "    \n",
    "      # Initialize best_paths matrix to zero\n",
    "      # POS tags as the rows, number of words in the corpus as columns\n",
    "      # the two matrices have the same size\n",
    "    best_paths = np.zeros((num_tags, len(corpus)), dtype=int)\n",
    "    \n",
    "      # Define the start token\n",
    "    s_idx = states.index(\"--s--\")\n",
    "    \n",
    "      # Go through each of the POS tags (matrix rows)\n",
    "    for i in range(num_tags): \n",
    "        \n",
    "          # Handle the special case when the transition from start token to POS tag i is zero\n",
    "          # Column zero of `best_probs` is initialized with the assumption that the first word \n",
    "          # of the corpus was preceded by a start token (\"--s--\"). \n",
    "          # This allows  to reference the A matrix for the transition probability\n",
    "        if A[s_idx,i] == 0: \n",
    "            \n",
    "              # Initialize best_probs at POS tag 'i', column 0, to negative infinity (log 0)\n",
    "            best_probs[i,0] = float('-inf')\n",
    "        \n",
    "          # For all other cases when transition from start token to POS tag i is non-zero:\n",
    "        else:\n",
    "            \n",
    "              # Initialize best_probs at POS tag 'i', column 0\n",
    "              # Check the formula above\n",
    "            best_probs[i,0] = math.log(A[s_idx,i]) + math.log(B[i,vocab[corpus[0]]] )\n",
    "                        \n",
    "    return best_probs, best_paths"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "best_probs, best_paths = initialize(tags, tagCounts, A, B, tw_prepr, vocabulary)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Viterbi Forward\n",
    "\n",
    "Now we will implement the `viterbi_forward` segment. In other words, we will populate the `best_probs` and `best_paths` matrices:\n",
    "- Walk forward through the corpus.\n",
    "- For each word, compute a probability for each possible tag. \n",
    "- This will include the path up to that (word,tag) combination. \n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The formula to compute the probability and path for the $i^{th}$ word in the $corpus$, the prior word $i-1$ in the corpus, current POS tag $j$, and previous POS tag $k$ is:\n",
    "\n",
    "$\\mathrm{prob} = \\mathbf{best\\_prob}_{k, i-1} + \\mathrm{log}(\\mathbf{A}_{k, j}) + \\mathrm{log}(\\mathbf{B}_{j, vocab(corpus_{i})})$\n",
    "\n",
    "where $corpus_{i}$ is the word in the corpus at index $i$, and $vocab$ is the dictionary that gets the unique integer that represents a given word.\n",
    "\n",
    "$\\mathrm{path} = k$\n",
    "\n",
    "where $k$ is the integer representing the previous POS tag.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "def viterbi_forward(A, B, test_corpus, best_probs, best_paths, vocab):\n",
    "    '''\n",
    "    Scope: \n",
    "        store the best_path and best_prob for every possible tag for each word \n",
    "        in the matrices `best_probs` and `best_tags`\n",
    "    Input: \n",
    "        A, B: The transiton and emission matrices respectively\n",
    "        test_corpus: a list containing a preprocessed corpus\n",
    "        best_probs: an initialized matrix of dimension (num_tags, len(corpus))\n",
    "        best_paths: an initialized matrix of dimension (num_tags, len(corpus))\n",
    "        vocab: a dictionary where keys are words in vocabulary and value is an index \n",
    "    Output: \n",
    "        best_probs: a completed matrix of dimension (num_tags, len(corpus))\n",
    "        best_paths: a completed matrix of dimension (num_tags, len(corpus))\n",
    "    '''\n",
    "      # Get the number of unique POS tags (which is the num of rows in best_probs)\n",
    "    num_tags = best_probs.shape[0]\n",
    "    \n",
    "      # Go through every word in the corpus starting from word 1\n",
    "      # Recall that word 0 was specially initialized in `initialize()`\n",
    "    for i in range(1, len(test_corpus)): \n",
    "        \n",
    "          # For PROGRESS: Print number of words processed, every 5000 words\n",
    "        if i % 5000 == 0:\n",
    "            print(\"Words processed: {:>8}\".format(i))\n",
    "            \n",
    "          # For each unique POS tag that the current word can be\n",
    "        for j in range(num_tags): \n",
    "            \n",
    "              # Initialize best_prob for word i to negative infinity\n",
    "            best_prob_i =  float(\"-inf\")\n",
    "            \n",
    "              # Initialize best_path for current word i to None\n",
    "            best_path_i = None\n",
    "\n",
    "              # For each POS tag that the previous word can be:\n",
    "            for k in range(num_tags): \n",
    "            \n",
    "                  # compute the probability that the previous word had a given POS tag, \n",
    "                  # that the current word has a given POS tag, \n",
    "                  # and that the POS tag would emit this current word.\n",
    "                \n",
    "                  # Probability = \n",
    "                  # best probs of POS tag k, previous word i-1 + \n",
    "                  # log(prob of transition from POS k to POS j) + \n",
    "                  # log(prob that emission of POS j is word i)\n",
    "                prob = best_probs[k,i-1] + math.log(A[k,j]) + math.log(B[j,vocab[test_corpus[i]]])\n",
    "                \n",
    "                  # retain the highest probability computed for the current word\n",
    "                if prob > best_prob_i: \n",
    "                    \n",
    "                    best_prob_i = prob\n",
    "                    \n",
    "                      # set best_paths to the index 'k', keep track of the POS tag of the previous word\n",
    "                      # that is part of the best path.  \n",
    "                      # K is representing the POS tag of the previous word which produced the highest probability \n",
    "                    best_path_i = k\n",
    "\n",
    "              # Save the best probability for the \n",
    "              # given current word's POS tag\n",
    "              # and the position of the current word inside the corpus\n",
    "            best_probs[j,i] = best_prob_i\n",
    "            \n",
    "              # Save the unique integer ID of the previous POS tag\n",
    "              # into best_paths matrix, for the POS tag of the current word\n",
    "              # and the position of the current word inside the corpus\n",
    "            best_paths[j,i] = best_path_i\n",
    "\n",
    "    return best_probs, best_paths"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Run the `viterbi_forward` function to fill in the `best_probs` and `best_paths` matrices.\n",
    "\n",
    "**Note** that this will take a few minutes to run.  There are about 30,000 words to process."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Words processed:     5000\n",
      "Words processed:    10000\n",
      "Words processed:    15000\n",
      "Words processed:    20000\n",
      "Words processed:    25000\n",
      "Words processed:    30000\n"
     ]
    }
   ],
   "source": [
    "# this will take a few minutes to run => processes ~ 30,000 words\n",
    "best_probs, best_paths = viterbi_forward(A, B, tw_prepr, best_probs, best_paths, vocabulary)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##  Viterbi backward\n",
    "\n",
    "The Viterbi backward algorithm gets the predictions of the POS tags for each word in the corpus using the `best_paths` and the `best_probs` matrices.\n",
    "  \n",
    "The backward pass help retrieve the most likely sequence of parts of speech tags for your given sequence of words.  \n",
    "- First it calculates the index of the entry with the highest probability in the last column of best_probs.  \n",
    "It represents the last hidden state we traversed when we observe the word\n",
    "- This index is used to traverse back through the best_paths matrix to reconstruct the sequence of parts of speech tags\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "def viterbi_backward(best_probs, best_paths, corpus, states):\n",
    "    '''\n",
    "    Scope: \n",
    "        This function retrieves the best path.\n",
    "    Input: \n",
    "        corpus: a list containing a preprocessed corpus\n",
    "        best_probs: an initialized matrix of dimension (num_tags, len(corpus))\n",
    "        best_paths: an initialized matrix of dimension (num_tags, len(corpus))\n",
    "        states: dictionary with each POS tag and its index \n",
    "    Output: \n",
    "        pred: returns a list of predicted POS tags for each word in the corpus.   \n",
    "    '''\n",
    "    \n",
    "  #  \n",
    "  # Initialization\n",
    "  #\n",
    "\n",
    "      # Get the number of words in the corpus\n",
    "      # which is also the number of columns in best_probs, best_paths\n",
    "    m = best_paths.shape[1] \n",
    "    \n",
    "      # Get the number of unique POS tags\n",
    "    num_tags = best_probs.shape[0]\n",
    "    \n",
    "      # Initialize the best probability for the last word\n",
    "    best_prob_for_last_word = float('-inf')\n",
    "    \n",
    "      # Initialize array z, same length as the corpus\n",
    "    z = [None] * m\n",
    "    \n",
    "      # Initialize pred array, same length as corpus\n",
    "    pred = [None] * m\n",
    "  \n",
    "  #\n",
    "  # Step 1 : Loop through all the rows (POS tags) in the last entry of `best_probs` \n",
    "  # and find the row (POS tag) with the maximum value. This is the best POS tag for the last word\n",
    "  #\n",
    "    \n",
    "      # Go through each POS tag for the *last* word (last column of best_probs)\n",
    "      # in order to find the row (POS tag integer ID) \n",
    "      # with highest probability for the last word\n",
    "    for k in range(num_tags):\n",
    "        \n",
    "\n",
    "          # If the probability of POS tag at row k \n",
    "          # is better than the previosly best probability for the last word:\n",
    "        if best_probs[k, m - 1] > best_prob_for_last_word:\n",
    "            \n",
    "              # then store the new best probability for the last word\n",
    "            best_prob_for_last_word = best_probs[k, m - 1]\n",
    "    \n",
    "              # and store the unique integer ID of the POS tag\n",
    "              # which is also the row number in best_probs\n",
    "            z[m - 1] = k\n",
    "            \n",
    "            \n",
    "      # Convert the last word's predicted POS tag\n",
    "      # from its unique integer ID into the string representation\n",
    "      # using the 'states' dictionary\n",
    "      # Store this in the 'pred' array for the last word\n",
    "    pred[m - 1] = states[z[m - 1]]\n",
    "    \n",
    "  #\n",
    "  # Step 2: traverse back through the best_paths matrix and retrieve all POS tags\n",
    "  #\n",
    "    \n",
    "      # Find all the best POS tags by walking backward through the best_paths\n",
    "      # From the last word in the corpus to the first word in the corpus\n",
    "    for i in range(m-1, -1, -1): \n",
    "        \n",
    "          # Retrieve the unique integer ID of\n",
    "          # the POS tag for the word at position 'i' in the corpus\n",
    "        pos_tag_for_word_i = z[i]\n",
    "        \n",
    "        \n",
    "          # In best_paths, go to the row representing the POS tag of word i\n",
    "          # and the column representing the word's position in the corpus\n",
    "          # to retrieve the predicted POS for the word at position i-1 in the corpus\n",
    "        z[i - 1] = best_paths[pos_tag_for_word_i,i]\n",
    "        \n",
    "          # Get the previous word's POS tag in string form\n",
    "          # again using the 'states' dictionary, \n",
    "          # where the key is the unique integer ID of the POS tag,\n",
    "          # and the value is the string representation of that POS tag\n",
    "        pred[i - 1] = states[z[i - 1]]\n",
    "        \n",
    "    return pred"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The prediction for ['see', 'them', 'here', 'with', 'us', '.'] is: \n",
      " ['VB', 'PRP', 'RB', 'IN', 'PRP', '.'] \n",
      "\n",
      "The prediction for ['The', 'economy', \"'s\", 'temperature', 'will', 'be', 'taken'] is: \n",
      " ['DT', 'NN', 'POS', 'NN', 'MD', 'VB', 'VBN']\n"
     ]
    }
   ],
   "source": [
    "# Run and test the function\n",
    "pred = viterbi_backward(best_probs, best_paths, tw_prepr, tags)\n",
    "\n",
    "\n",
    "m=len(pred)\n",
    "print(f\"The prediction for {tw_prepr[-7:m-1]} is: \\n {pred[-7:m-1]} \\n\")\n",
    "print(f\"The prediction for {tw_prepr[0:7]} is: \\n {pred[0:7]}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Predict on single words or sentences\n",
    "  \n",
    "Let's see a couple of examples:  \n",
    "In general the list *pred* just retrieved from the Viterbi algorith running on the training corpus can be used to check a word POS, knowing the word index:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The third word is: temperature\n",
      "Its prediction for the POS tag is: NN\n",
      "The corresponding true label is:  temperature\tNN\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print('The third word is:', tw_prepr[3])\n",
    "print('Its prediction for the POS tag is:', pred[3])\n",
    "print('The corresponding true label is: ', testing_corpus[3])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Obviously you don't know the word index in advance, so it can be retrieved from the training word preprocessed dictionary (*tw_prepr*).  \n",
    "Let's do a quick helper function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "def getWordPOS(word):\n",
    "    if word in tw_prepr:\n",
    "        return pred[tw_prepr.index(word)]\n",
    "    else:\n",
    "        return \"unknown\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'unknown'"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "getWordPOS(\"cat\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'NN'"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "getWordPOS(\"work\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Same can be done for an entire sentence.  \n",
    "The following helper function will split a sentence (string) into words and run the Viterbi algorithm on them:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "def getSentencePOS(sentence):\n",
    "    \"\"\"\n",
    "    Input: \n",
    "        sentence: the sentence to be tagged. String. Needs a marker at the end (newline).\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",
    "    corpus = preprocessCorpus(words)\n",
    "    \n",
    "    best_probs, best_paths = initialize(tags, tagCounts, A, B, corpus, vocabulary)\n",
    "    best_probs, best_paths = viterbi_forward(A, B, corpus, best_probs, best_paths, vocabulary)\n",
    "    predictedPOS = viterbi_backward(best_probs, best_paths, corpus, tags)\n",
    "                \n",
    "            # return a list of tuples: (word, POS)\n",
    "    return predictedPOS"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['PRP', 'VBP', 'DT', 'JJ', 'NNS', '#']\n"
     ]
    }
   ],
   "source": [
    "print(getSentencePOS(\"I have a black cat \\n\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['PRP', 'VBP', 'IN', 'NNP', '#']\n"
     ]
    }
   ],
   "source": [
    "print(getSentencePOS(\"I work in Shanghai \\n\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And here you can see that the sentence previously failing **is now working!**  \n",
    "'work' is not only a Noun, in this case is a Verb and is correctly identified.  \n",
    "  \n",
    "Now we can check the overall accuracy on the testing dataset and see if it improved against the previous simpler model (we check it in the same way)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#  Predicting on a data set\n",
    "\n",
    "Finally we compute the accuracy of the viterbi algorithm's POS tag predictions by comparing it with the true labels.  \n",
    "`pred` is the list of predicted POS tags corresponding to the words of the `test_corpus`.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "def compute_accuracy(pred, y):\n",
    "    '''\n",
    "    Input: \n",
    "        pred: a list of the predicted parts-of-speech \n",
    "        y: a list of lines where each word is separated by a '\\t' (i.e. word \\t tag)\n",
    "    Output: \n",
    "        \n",
    "    '''\n",
    "    num_correct = 0\n",
    "    total = 0\n",
    "    \n",
    "      # Zip together the prediction and the labels\n",
    "    for prediction, y in zip(pred, y):\n",
    "\n",
    "          # Split the label into the word and the POS tag\n",
    "        word_tag_tuple = y.split()\n",
    "        \n",
    "          # Check that there is actually a word and a tag\n",
    "          # no more and no less than 2 items\n",
    "        if len(word_tag_tuple) != 2: # complete this line\n",
    "            continue \n",
    "        \n",
    "          # store the word and tag separately\n",
    "        word, tag = word_tag_tuple\n",
    "          # Check if the POS tag label matches the prediction\n",
    "        if prediction == tag: \n",
    "              # count the number of times that the prediction\n",
    "              # and label match\n",
    "            num_correct += 1\n",
    "            \n",
    "          # keep track of the total number of examples (that have valid labels)\n",
    "        total += 1\n",
    "        \n",
    "    return (num_correct/total)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Accuracy of the Viterbi algorithm is 0.9531\n"
     ]
    }
   ],
   "source": [
    "print(f\"Accuracy of the Viterbi algorithm is {compute_accuracy(pred, testing_corpus):.4f}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you can see we are able to classify the parts-of-speech with **95% accuracy**, which is an improvement above the previous model."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### References\n",
    "\n",
    "Here we predicted POS tags by walking forward through a corpus and knowing the previous word (Viterbi algorithm and Hidden Markov Model).  \n",
    "There are other implementations that use bidirectional POS tagging.  \n",
    "Bidirectional POS tagging requires knowing the previous word **and the next word** in the corpus when predicting the current word's POS tag.\n",
    "Bidirectional POS tagging would tell you more about the POS and be more accurate. It can be implemented starting from the algorith above.  \n",
    "\n",
    "- [\"Speech and Language Processing\", Dan Jurafsky and James H. Martin](https://web.stanford.edu/~jurafsky/slp3/)"
   ]
  }
 ],
 "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
}