week_3/out-of-vocabulary-words.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name=\"oov-words\"></a>\n",
    "# Out of vocabulary words (OOV)\n",
    "<a name=\"vocabulary\"></a>\n",
    "### Vocabulary\n",
    "In the video about the out of vocabulary words, you saw that the first step in dealing with the unknown words is to decide which words belong to the vocabulary. \n",
    "\n",
    "In the code assignment, you will try the method based on minimum frequency - all words appearing in the training set with frequency >= minimum frequency are added to the vocabulary.\n",
    "\n",
    "Here is a code for the other method, where the target size of the vocabulary is known in advance and the vocabulary is filled with words based on their frequency in the training set."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "the new vocabulary containing 3 most frequent words: ['happy', 'because', 'learning']\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# build the vocabulary from M most frequent words\n",
    "# use Counter object from the collections library to find M most common words\n",
    "from collections import Counter\n",
    "\n",
    "# the target size of the vocabulary\n",
    "M = 3\n",
    "\n",
    "# pre-calculated word counts\n",
    "# Counter could be used to build this dictionary from the source corpus\n",
    "word_counts = {'happy': 5, 'because': 3, 'i': 2, 'am': 2, 'learning': 3, '.': 1}\n",
    "\n",
    "vocabulary = Counter(word_counts).most_common(M)\n",
    "\n",
    "# remove the frequencies and leave just the words\n",
    "vocabulary = [word for word, frequency in vocabulary]\n",
    "\n",
    "print(f\"the new vocabulary containing {M} most frequent words: {vocabulary}\\n\") \n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that the vocabulary is ready, you can use it to replace the OOV words with $<UNK>$ as you saw in the lecture."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "input sentence: ['am', 'i', 'learning']\n",
      "output sentence: ['<UNK>', '<UNK>', 'learning']\n"
     ]
    }
   ],
   "source": [
    "# test if words in the input sentences are in the vocabulary, if OOV, print <UNK>\n",
    "sentence = ['am', 'i', 'learning']\n",
    "output_sentence = []\n",
    "print(f\"input sentence: {sentence}\")\n",
    "\n",
    "for w in sentence:\n",
    "    # test if word w is in vocabulary\n",
    "    if w in vocabulary:\n",
    "        output_sentence.append(w)\n",
    "    else:\n",
    "        output_sentence.append('<UNK>')\n",
    "        \n",
    "print(f\"output sentence: {output_sentence}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When building the vocabulary in the code assignment, you will need to know how to iterate through the word counts dictionary. \n",
    "\n",
    "Here is an example of a similar task showing how to go through all the word counts and print out only the words with the frequency equal to f. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "because\n",
      "learning\n"
     ]
    }
   ],
   "source": [
    "# iterate through all word counts and print words with given frequency f\n",
    "f = 3\n",
    "\n",
    "word_counts = {'happy': 5, 'because': 3, 'i': 2, 'am': 2, 'learning':3, '.': 1}\n",
    "\n",
    "for word, freq in word_counts.items():\n",
    "    if freq == f:\n",
    "        print(word)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As mentioned in the videos, if there are many $<UNK>$ replacements in your train and test set, you may get a very low perplexity even though the model itself wouldn't be very helpful. \n",
    "    \n",
    "Here is a sample code showing this unwanted effect. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "perplexity for the training set: 1.2599210498948732\n",
      "perplexity for the training set with <UNK>: 1.0\n"
     ]
    }
   ],
   "source": [
    "# many <unk> low perplexity \n",
    "training_set = ['i', 'am', 'happy', 'because','i', 'am', 'learning', '.']\n",
    "training_set_unk = ['i', 'am', '<UNK>', '<UNK>','i', 'am', '<UNK>', '<UNK>']\n",
    "\n",
    "test_set = ['i', 'am', 'learning']\n",
    "test_set_unk = ['i', 'am', '<UNK>']\n",
    "\n",
    "M = len(test_set)\n",
    "probability = 1\n",
    "probability_unk = 1\n",
    "\n",
    "# pre-calculated probabilities\n",
    "bigram_probabilities = {('i', 'am'): 1.0, ('am', 'happy'): 0.5, ('happy', 'because'): 1.0, ('because', 'i'): 1.0, ('am', 'learning'): 0.5, ('learning', '.'): 1.0}\n",
    "bigram_probabilities_unk = {('i', 'am'): 1.0, ('am', '<UNK>'): 1.0, ('<UNK>', '<UNK>'): 0.5, ('<UNK>', 'i'): 0.25}\n",
    "\n",
    "# go through the test set and calculate its bigram probability\n",
    "for i in range(len(test_set) - 2 + 1):\n",
    "    bigram = tuple(test_set[i: i + 2])\n",
    "    probability = probability * bigram_probabilities[bigram]\n",
    "        \n",
    "    bigram_unk = tuple(test_set_unk[i: i + 2])\n",
    "    probability_unk = probability_unk * bigram_probabilities_unk[bigram_unk]\n",
    "\n",
    "# calculate perplexity for both original test set and test set with <UNK>\n",
    "perplexity = probability ** (-1 / M)\n",
    "perplexity_unk = probability_unk ** (-1 / M)\n",
    "\n",
    "print(f\"perplexity for the training set: {perplexity}\")\n",
    "print(f\"perplexity for the training set with <UNK>: {perplexity_unk}\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name=\"smoothing\"></a>\n",
    "### Smoothing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Add-k smoothing was described as a method for smoothing of the probabilities for previously unseen n-grams. \n",
    "\n",
    "Here is an example code that shows how to implement add-k smoothing but also highlights a disadvantage of this method. The downside is that n-grams not previously seen in the training dataset get too high probability. \n",
    "\n",
    "In the code output bellow you'll see that a phrase that is in the training set gets the same probability as an unknown phrase."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "probability_known_trigram: 0.2\n",
      "probability_unknown_trigram: 0.2\n"
     ]
    }
   ],
   "source": [
    "def add_k_smooting_probability(k, vocabulary_size, n_gram_count, n_gram_prefix_count):\n",
    "    numerator = n_gram_count + k\n",
    "    denominator = n_gram_prefix_count + k * vocabulary_size\n",
    "    return numerator / denominator\n",
    "\n",
    "trigram_probabilities = {('i', 'am', 'happy') : 2}\n",
    "bigram_probabilities = {( 'am', 'happy') : 10}\n",
    "vocabulary_size = 5\n",
    "k = 1\n",
    "\n",
    "probability_known_trigram = add_k_smooting_probability(k, vocabulary_size, trigram_probabilities[('i', 'am', 'happy')], \n",
    "                           bigram_probabilities[( 'am', 'happy')])\n",
    "\n",
    "probability_unknown_trigram = add_k_smooting_probability(k, vocabulary_size, 0, 0)\n",
    "\n",
    "print(f\"probability_known_trigram: {probability_known_trigram}\")\n",
    "print(f\"probability_unknown_trigram: {probability_unknown_trigram}\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name=\"backoff\"></a>\n",
    "### Back-off\n",
    "Back-off is a model generalization method that leverages information from lower order n-grams in case information about the high order n-grams is missing. For example, if the probability of an trigram is missing, use bigram information and so on.\n",
    "\n",
    "Here you can see an example of a simple back-off technique."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "besides the trigram ('are', 'you', 'happy') we also use bigram ('you', 'happy') and unigram (happy)\n",
      "\n",
      "probability for trigram ('are', 'you', 'happy') not found\n",
      "probability for bigram ('you', 'happy') not found\n",
      "probability for unigram happy found\n",
      "\n",
      "probability for trigram ('are', 'you', 'happy') estimated as 0.06400000000000002\n"
     ]
    }
   ],
   "source": [
    "# pre-calculated probabilities of all types of n-grams\n",
    "trigram_probabilities = {('i', 'am', 'happy'): 0}\n",
    "bigram_probabilities = {( 'am', 'happy'): 0.3}\n",
    "unigram_probabilities = {'happy': 0.4}\n",
    "\n",
    "# this is the input trigram we need to estimate\n",
    "trigram = ('are', 'you', 'happy')\n",
    "\n",
    "# find the last bigram and unigram of the input\n",
    "bigram = trigram[1: 3]\n",
    "unigram = trigram[2]\n",
    "print(f\"besides the trigram {trigram} we also use bigram {bigram} and unigram ({unigram})\\n\")\n",
    "\n",
    "# 0.4 is used as an example, experimentally found for web-scale corpuses when using the \"stupid\" back-off\n",
    "lambda_factor = 0.4\n",
    "probability_hat_trigram = 0\n",
    "\n",
    "# search for first non-zero probability starting with trigram\n",
    "# to generalize this for any order of n-gram hierarchy, \n",
    "# you could loop through the probability dictionaries instead of if/else cascade\n",
    "if trigram not in trigram_probabilities or trigram_probabilities[trigram] == 0:\n",
    "    print(f\"probability for trigram {trigram} not found\")\n",
    "    \n",
    "    if bigram not in bigram_probabilities or bigram_probabilities[bigram] == 0:\n",
    "        print(f\"probability for bigram {bigram} not found\")\n",
    "        \n",
    "        if unigram in unigram_probabilities:\n",
    "            print(f\"probability for unigram {unigram} found\\n\")\n",
    "            probability_hat_trigram = lambda_factor * lambda_factor * unigram_probabilities[unigram]\n",
    "        else:\n",
    "            probability_hat_trigram = 0\n",
    "    else:\n",
    "        probability_hat_trigram = lambda_factor * bigram_probabilities[bigram]\n",
    "else:\n",
    "    probability_hat_trigram = trigram_probabilities[trigram]\n",
    "\n",
    "print(f\"probability for trigram {trigram} estimated as {probability_hat_trigram}\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name=\"interpolation\"></a>\n",
    "### Interpolation\n",
    "The other method for using probabilities of lower order n-grams is the interpolation. In this case, you use weighted probabilities of n-grams of all orders every time, not just when high order information is missing. \n",
    "\n",
    "For example, you always combine trigram, bigram and unigram probability. You can see how this in the following code snippet."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "besides the trigram ('i', 'am', 'happy') we also use bigram ('am', 'happy') and unigram (happy)\n",
      "\n",
      "estimated probability of the input trigram ('i', 'am', 'happy') is 0.12\n"
     ]
    }
   ],
   "source": [
    "# pre-calculated probabilities of all types of n-grams\n",
    "trigram_probabilities = {('i', 'am', 'happy'): 0.15}\n",
    "bigram_probabilities = {( 'am', 'happy'): 0.3}\n",
    "unigram_probabilities = {'happy': 0.4}\n",
    "\n",
    "# the weights come from optimization on a validation set\n",
    "lambda_1 = 0.8\n",
    "lambda_2 = 0.15\n",
    "lambda_3 = 0.05\n",
    "\n",
    "# this is the input trigram we need to estimate\n",
    "trigram = ('i', 'am', 'happy')\n",
    "\n",
    "# find the last bigram and unigram of the input\n",
    "bigram = trigram[1: 3]\n",
    "unigram = trigram[2]\n",
    "print(f\"besides the trigram {trigram} we also use bigram {bigram} and unigram ({unigram})\\n\")\n",
    "\n",
    "# in the production code, you would need to check if the probability n-gram dictionary contains the n-gram\n",
    "probability_hat_trigram = lambda_1 * trigram_probabilities[trigram] \n",
    "+ lambda_2 * bigram_probabilities[bigram]\n",
    "+ lambda_3 * unigram_probabilities[unigram]\n",
    "\n",
    "print(f\"estimated probability of the input trigram {trigram} is {probability_hat_trigram}\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's it for week 3, you should be ready now for the code assignment. "
   ]
  }
 ],
 "metadata": {
  "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.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}