1-language_model.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# A review of probability theory\n",
    "\n",
    "Say we need to model flipping a coin. We might express it with:\n",
    "\n",
    "$P(x=\\text{heads})=0.5$\n",
    "\n",
    "$P(x=\\text{tails})=0.5$\n",
    "\n",
    "The discrete random variable $x$ denotes the possible outcomes, which is either heads or tails in this scenario.\n",
    "\n",
    "The function $P(\\cdot)$ outputs the probability of the outcome.\n",
    "\n",
    "In flipping coins, the events are independent, which means each flip of a coin does not affect the probability of any future flip."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Conditional Probability\n",
    "\n",
    "However, drawing a card from a deck does affect the next draw.\n",
    "\n",
    "What is the probability of drawing a King from a deck of poker cards?\n",
    "\n",
    "$P(x_0=\\text{any King})=4/52=1/13$\n",
    "\n",
    "What is the probability of drawing a King after already drawing a King of Heart?\n",
    "\n",
    "$P(x_1=\\text{any King}|x_0=\\text{King of Heart})=3/51$, where $x_0$ denotes the first draw and $x_1$ denotes the second draw\n",
    "\n",
    "Drawing a king of heart affects all future draws. This is modeled using conditional probability. \n",
    "\n",
    "$P(x_1|x_0)$ is the probability of $x_1$ happening given $x_0$ already happened.\n",
    "\n",
    "Note that $P(x_1|x_0)$ also implies that any other random variable other than $x_0$ has no impact on the probability of $x_1$.\n",
    "\n",
    "Meaning $x_1$ is dependent on $x_0$, and $x_1$ is independent from any other random variables.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Language model\n",
    "One of the most influential idea from statistical NLP is the idea to model language with conditional probability. This idea extends even to neural NLP.\n",
    "\n",
    "In NLP, we want a way to evaluate whether a given sentence is a valid sentence.\n",
    "\n",
    "What is the probability of the sentence \"An apple is sweet.\" is a valid sentence?\n",
    "\n",
    "What is the probability of the sentence \"apple sweet An is.\" is a valid sentence?\n",
    "\n",
    "While it is unclear what the exact value should be, most people would agree $P(\\text{\"apple sweet An is.\"})$ should be a lot lower than $P(\\text{\"An apple is sweet.\"})$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are different ways to assign/calculate probability: [frequentist probability](https://en.wikipedia.org/wiki/Frequentist_probability), [Bayesian probability](https://en.wikipedia.org/wiki/Bayesian_probability), [classical definition of probability](https://en.wikipedia.org/wiki/Classical_definition_of_probability).\n",
    "\n",
    "We will be using the frequentist probability:\n",
    "$$P(x) \\approx \\frac{n_x}{n_t}$$\n",
    "\n",
    "Where $n_x$ is the number of outcomes which $x$ happened, and $n_t$ is the total number of trials.\n",
    "\n",
    "Under this view, the probability of the sentence \"An apple is sweet.\" is a valid sentence might be approximated by:\n",
    "\n",
    "$$P(\\text{\"An apple is sweet.\"}) \\approx \\frac{\\text{# of \"An apple is sweet.\" sentence}}{\\text{# of sentence in existence}}$$\n",
    "\n",
    "However, this may not be a good idea. Just because no one has written a particular sentence does not mean it is not a valid sentence.\n",
    "\n",
    "Maybe no one ever wrote the sentence: \"Bart walked down to Kwik-E-Mart and bought an apple from Apu.\", which would mean it gets a probability of 0. But that does not mean it is not a valid sentence that some one might write.\n",
    "\n",
    "Clearly, a smarter way is needed. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Language model: unigram\n",
    "One idea is to break down the probability of the sentence into probability of the words.\n",
    "\n",
    "$P(x_0 = \\text{An}, x_1 = \\text{apple}, x_2 = \\text{is}, x_3 = \\text{sweet}) = P(x_i = \\text{An})P(x_i = \\text{apple})P(x_i = \\text{A})P(x_i = \\text{is})P(x_i = \\text{sweet})$\n",
    "\n",
    "This is usually written in a more compact form in NLP:\n",
    "\n",
    "$P(\\text{An apple is sweet}) = P(\\text{An})P(\\text{apple})P(\\text{is})P(\\text{sweet})$\n",
    "\n",
    "The above formula assumes the probability of each word is independent. Meaning it does not consider the context that the word occur in."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementing unigram\n",
    "\n",
    "We will be using the newsgroup dataset. We will break down each post into sentences then tokenize each word and lemmatize the tokens. We are also going to convert all uppercase to lowercase. This is to reduce variation for the same word.\n",
    "\n",
    "Under frequentist probability we could assign the probability of the word \"apple\" to:\n",
    "\n",
    "$$P(apple) \\approx \\frac{\\text{# of \"apple\"}}{\\text{# of words}}$$\n",
    "\n",
    "So we will need a count of the words. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "[nltk_data] Downloading package punkt to data...\n",
      "[nltk_data]   Package punkt is already up-to-date!\n",
      "[nltk_data] Downloading package wordnet to data...\n",
      "[nltk_data]   Package wordnet is already up-to-date!\n"
     ]
    }
   ],
   "source": [
    "import math\n",
    "from collections import defaultdict\n",
    "\n",
    "import nltk\n",
    "from nltk.stem import WordNetLemmatizer\n",
    "from sklearn.datasets import fetch_20newsgroups\n",
    "\n",
    "dataset = fetch_20newsgroups(data_home='data', remove=('headers', 'footers', 'quotes'))\n",
    "\n",
    "nltk.data.path.append('data')\n",
    "nltk.download('punkt', download_dir='data')\n",
    "nltk.download('wordnet', download_dir='data')\n",
    "lemmatizer = WordNetLemmatizer() \n",
    "\n",
    "num_post = 100  # Only process this many posts. Saves time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Just like spaCy, nltk is NLP package for python. \n",
    "\n",
    "It features much more algorithm that spaCy, but it is less optimized. \n",
    "\n",
    "It was developed for statistical NLP."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "total_count = 0\n",
    "word_count = defaultdict(int)\n",
    "for post in dataset.data[:num_post]:\n",
    "    sents = nltk.sent_tokenize(post)\n",
    "    for sent in sents:\n",
    "        tokens = nltk.word_tokenize(sent.lower())\n",
    "        for token in tokens:\n",
    "            word_count[lemmatizer.lemmatize(token)] += 1\n",
    "            total_count += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we have counted the words, we have a probability for each word in our data.\n",
    "\n",
    "What is the probability for the word \"if\"?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.002851033499643621"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "word = \"if\"\n",
    "\n",
    "word_count[word] / total_count  # The probability of the word according to our formula"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$P(\\text{if})$ is 0.285% according to the model we have trained with the data given.\n",
    "\n",
    "What is the probability of the sentence: \"What is that car?\"?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Probability of \"What is that car?\": 1.1210876923308169e-12\n"
     ]
    }
   ],
   "source": [
    "sent = \"What is that car?\"\n",
    "\n",
    "prob = 1\n",
    "for token in nltk.word_tokenize(sent.lower()):\n",
    "    unigram_prob = word_count[lemmatizer.lemmatize(token)] / total_count\n",
    "    prob *= unigram_prob\n",
    "\n",
    "print(f\"Probability of \\\"{sent}\\\": {prob}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Log probability\n",
    "\n",
    "The probability of that sentence is quite small. For some sentence, the probability might be so small as to underflow. Therefore, log probability is used for numerical stability reasons.\n",
    "\n",
    "$\\text{log}(x \\cdot y) = \\text{log}(x) + \\text{log}(y)$\n",
    "\n",
    "Instead of multiplying probabilities, we will be adding log probabilities."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Log probability of \"What is that car?\": -27.51672174801957\n"
     ]
    }
   ],
   "source": [
    "sent = \"What is that car?\"\n",
    "\n",
    "prob = 0\n",
    "for token in nltk.word_tokenize(sent.lower()):\n",
    "    unigram_prob = math.log(word_count[lemmatizer.lemmatize(token)] / total_count)\n",
    "    prob += unigram_prob\n",
    "\n",
    "print(f\"Log probability of \\\"{sent}\\\": {prob}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Smoothing\n",
    "\n",
    "What is the probability of the word \"jupyter\"?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.0"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "word = \"jupyter\"\n",
    "\n",
    "word_count[word] / total_count "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The probability should be 0. As our model never saw the word \"jupyter\". \n",
    "\n",
    "In other words, any sentence with an unknown word to the model has a probability of 0. This is undesirable as a single unknown word should not ruin an otherwise good sentence."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To deal with unknown words, smoothing is used. There are a variety of smoothing techniques. We will be using add-one smoothing:\n",
    "\n",
    "$$P(x) = \\frac{\\text{# of }x + 1}{\\text{# of words} + \\text{vocab size}}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The # of words refers to how many words in the dataset.\n",
    "\n",
    "The vocab size refers to how many types of word in the dataset.\n",
    "\n",
    "For example, if the whole dataset is: \"apple apple. orange orange.\"\n",
    "\n",
    "\\# of words: 4\n",
    "\n",
    "vocab size: 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With add-one smoothing what is the probability of \"if\"?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.002407704654895666"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "word = \"if\"\n",
    "vocab_size = len(word_count)\n",
    "\n",
    "(word_count[word] + 1) / (total_count + vocab_size)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now the $P(\\text{if})$ becomes 0.241%. \n",
    "\n",
    "Note that this is slightly smaller than without add-one smoothing. What add-one smoothing and other smoothing are doing is taking a little bit of probability from known words and giving it to the unknown word category.\n",
    "\n",
    "All unknown words are given a fixed probability of $$\\frac{1}{\\text{# of words} + \\text{vocab size}}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Dealing with unknown without smoothing\n",
    "It is also possible give unknown words a fix probability of $\\frac{1}{\\text{vocab size}}$ without removing probability from other words. \n",
    "\n",
    "Technically, it would not be a probability as it no longer adds up to 1, but it works well in practice. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Practice:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise 1:\n",
    "What is the probability of \"What is that car?\" with add-one smoothing?\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Probability of \"What is that car?\": 4.821918666285085e-13\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise 2:\n",
    "What is the log probability of \"What is that car?\" with add-one smoothing?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Log probability of \"What is that car?\": -28.360259822125837"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem of unigram\n",
    "It was briefly mentioned that unigram doesn't consider the context of the word. It should be apparent now.\n",
    "\n",
    "The probability of of \"are\" in \"There are an apple.\" and \"There are apples.\" are the same. Even \"There are an apple\" is grammatically incorrect.\n",
    "\n",
    "Both are equal to $\\frac{\\text{# of \"are\"}}{\\text{# of words}}$ when without smoothing.\n",
    "\n",
    "There needs to be a way to consider the context of the given word."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Language model: n-gram\n",
    "\n",
    "Under the n-gram model, the probability of a word given the $n-1$ word(s) that comes before it.\n",
    "\n",
    "So a bigram ($n=2$) would look something like: \n",
    "\n",
    "$P(\\text{apple}|\\text{an})$\n",
    "\n",
    "A trigram ($n=3$) would look something like: \n",
    "\n",
    "$P(\\text{is}|\\text{an apple})$\n",
    "\n",
    "Which is the probability of the word \"is\" appearing given two word before it is \"a apple\".\n",
    "\n",
    "So the probability of $P(\\text{is}|\\text{an apple})$ should be a lot higher than $P(\\text{are}|\\text{an apple})$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Bigram\n",
    "\n",
    "For the $n=2$ case, the probability is written as:\n",
    "\n",
    "$P(w_i|w_{i-1})$\n",
    "\n",
    "Where $w_i$ is the word that follows $w_{i-1}$.\n",
    "\n",
    "Example: In \"an apple\", $w_i$ would be \"apple\", and $w_{i-1}$ would be \"an\".\n",
    "\n",
    "Under the bigram model, we are assuming that the probability of $w_i$ only depends on $w_{i-1}$.\n",
    "\n",
    "To calculate the probability of a sentence using bigram (conditional probability), we need chain rule.\n",
    "\n",
    "#### Chain rule\n",
    "\n",
    "$$P(X_n , \\dots , X_1) = P(X_n | X_{n-1} , \\dots , X_1) P(X_{n-1} , \\dots , X_1)$$\n",
    "\n",
    "So for 4 word sentence:\n",
    "$$P(w_0 w_1 w_2 w_3) = P(w_3|w_0 w_1 w_2) P(w_0 w_1 w_2) = P(w_3 | w_0 w_1 w_2) P(w_2 | w_0 w_1) P(w_0 w_1) = P(w_3 | w_0 w_1 w_2) P(w_2 | w_0 w_1) P(w_1 | w_0) P(w_0)$$\n",
    "\n",
    "In bigram, we are assuming each word is independent from every word except the word before it. So we can cancel all other words.\n",
    "\n",
    "$$P(w_0 w_1 w_2 w_3) = P(w_3|w_2) P(w_2|w_1)P(w_1|w_0)P(w_0) = P(w_0)P(w_1|w_0)P(w_2|w_1)P(w_3|w_2)$$\n",
    " \n",
    "\n",
    "The probability of the sentence \"An apple is sweet\" with bigram becomes:\n",
    "\n",
    "$$P(\\text{An apple is sweet}) = P(\\text{$<$S$>$}) P(\\text{An} | \\text{$<$S$>$})P(\\text{apple} | \\text{An})P(\\text{is} | \\text{apple})P(\\text{sweet} | \\text{is})$$\n",
    "\n",
    "Where $<$S$>$ denotes a special start symbol. Since there is no word that comes before \"An\". We will define $P($<$S$>$)$ as 1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementing bigram\n",
    "\n",
    "To calculate conditional probability, we will use the following formula:\n",
    "\n",
    "$$P(A|B)=\\frac{P(A, B)}{P(B)}$$\n",
    "\n",
    "For bigram that would be $$P(w_i|w_{i-1}) = \\frac{P(w_{i-1} w_i)}{P(w_{i-1})} \\approx \\frac{C(w_{i-1} w_i)}{C(w_{i-1})}$$\n",
    "\n",
    "Where $C( \\cdot )$ is the count function.\n",
    "\n",
    "So for $w_{i-1} = \\text{a}$, $w_i = \\text{apple}$:\n",
    "\n",
    "$$P(\\text{apple} | \\text{an}) \\approx \\frac{\\text{# of \"an apple\"}}{\\text{# of \"an\"}}$$\n",
    "\n",
    "So to calculate bigram, we need count of individual words and word pairs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "START_TOKEN = \"<S>\"\n",
    "\n",
    "total_count = 0\n",
    "word_count = defaultdict(int)\n",
    "pair_count = defaultdict(int)\n",
    "for post in dataset.data[:num_post]:\n",
    "    sents = nltk.sent_tokenize(post)\n",
    "    for sent in sents:\n",
    "        tokens = nltk.word_tokenize(sent.lower())\n",
    "        last_word = START_TOKEN\n",
    "        for token in tokens:\n",
    "            word = lemmatizer.lemmatize(token)\n",
    "            pair_count[(last_word, word)] += 1       \n",
    "            word_count[word] += 1\n",
    "            total_count += 1\n",
    "            last_word = word"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once the words and word pairs are counted we can calculate the bigram probability.\n",
    "\n",
    "What is the probability of \"is\" after the word \"what\"?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.04878048780487805"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "words = (\"what\", \"is\")\n",
    "\n",
    "pair_count[words] / word_count[words[0]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Backoff\n",
    "It is possible that a there is a unseen bigram, but the unigram is seen.\n",
    "\n",
    "In this case, we can use the unigram instead of bigram\n",
    "\n",
    "Say we need to evaluate \"day\" in \"good day\":"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.0"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "words = (\"good\", \"day\")\n",
    "\n",
    "pair_count[words] / word_count[words[0]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There is no such bigram in the data, so the probability is 0. In that case, we can use the unigram \"day\" to replace it. However, we need to weight it first.\n",
    "\n",
    "The easiest yet effective method is stupid back-off, which weight the probability by 0.4 each time we back off. \n",
    "\n",
    "So by going from bigram to unigram we multiple the unigram probability by 0.4."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What is the probability of \"day\" in \"good day\" with stupid back-off from bigram to unigram?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Probability: 0.00033541570584042597\n"
     ]
    }
   ],
   "source": [
    "words = (\"good\", \"day\")\n",
    "\n",
    "prob = pair_count[words] / word_count[words[0]]\n",
    "if prob == 0:\n",
    "    prob = 0.4 * word_count[words[1]] / total_count\n",
    "    \n",
    "print(f\"Probability: {prob}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The result from stupid back-off is not a true probability since all the outcomes no longer adds up to 1. There are back-offs which output true probabilities such as Katz's back-off."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Practice:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise 3:\n",
    "Train a trigram model.\n",
    "\n",
    "hint: $P(w_i|w_{i-2}w_{i-1}) = \\frac{C(w_{i-2}w_{i-1}w_i)}{C(w_{i-2}w_{i-1})}$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "# code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise 4:\n",
    "What is the probability of \"a\" after \"it is\"?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "# code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solutions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Probability of \"What is that car?\": 4.822760041028505e-13\n"
     ]
    }
   ],
   "source": [
    "# Solution to exercise 1\n",
    "sent = \"What is that car?\"\n",
    "vocab_size = len(word_count)\n",
    "\n",
    "prob = 1\n",
    "for token in nltk.word_tokenize(sent.lower()):\n",
    "    unigram_prob = (word_count[lemmatizer.lemmatize(token)] + 1) / (total_count + vocab_size)\n",
    "    prob *= unigram_prob\n",
    "\n",
    "print(f\"Probability of \\\"{sent}\\\": {prob}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Log probability of \"What is that car?\": -28.360259822125837\n"
     ]
    }
   ],
   "source": [
    "# Solution to exercise 2\n",
    "sent = \"What is that car?\"\n",
    "vocab_size = len(word_count)\n",
    "\n",
    "prob = 0\n",
    "for token in nltk.word_tokenize(sent.lower()):\n",
    "    unigram_prob = math.log((word_count[lemmatizer.lemmatize(token)] + 1) / (total_count + vocab_size))\n",
    "    prob += unigram_prob\n",
    "\n",
    "print(f\"Log probability of \\\"{sent}\\\": {prob}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution to exercise 3\n",
    "START_TOKEN = \"<S>\"\n",
    "\n",
    "context_count = defaultdict(int)\n",
    "phrase_count = defaultdict(int)\n",
    "for post in dataset.data[:num_post]:\n",
    "    sents = nltk.sent_tokenize(post)\n",
    "    for sent in sents:\n",
    "        tokens = nltk.word_tokenize(sent.lower())\n",
    "        second_last_word = START_TOKEN\n",
    "        last_word = START_TOKEN\n",
    "        for token in tokens:\n",
    "            word = lemmatizer.lemmatize(token)\n",
    "            phrase_count[(second_last_word, last_word, word)] += 1       \n",
    "            context_count[(second_last_word, last_word)] += 1 \n",
    "            second_last_word = last_word\n",
    "            last_word = word"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.07407407407407407"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Solution to exercise 4\n",
    "words = (\"it\", \"is\", \"a\")\n",
    "\n",
    "phrase_count[words] / context_count[(words[0], words[1])]"
   ]
  }
 ],
 "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}