1-foundations/Section 3.1 - n-Gram Language Models (basic).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "232b1b9c-4b24-4dd3-b003-5f30da66680c",
   "metadata": {},
   "source": [
    "<img src='data/images/section-notebook-header.png' />"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c8ab901a",
   "metadata": {},
   "source": [
    "# N-Gram Language Models (basic)\n",
    "\n",
    "A n-gram language model is a type of statistical language model that predicts the likelihood of a sequence of words based on the probability of occurrence of smaller word sequences called n-grams. An n-gram is a contiguous sequence of n items from a given sample of text, where the items can be words, characters, or even phonemes. In the context of language modeling, an n-gram typically refers to a sequence of n words. For example, in the sentence \"I love to play soccer,\" the 2-grams (or bigrams) would be \"I love,\" \"love to,\" \"to play,\" and \"play soccer.\" The 3-grams (or trigrams) would be \"I love to,\" \"love to play,\" and \"to play soccer.\"\n",
    "\n",
    "The n-gram language model makes assumptions about the probability of a word occurring based on the previous n-1 words. It utilizes a training corpus of text to calculate the frequencies of n-grams and estimates the probability of encountering a particular word given the preceding n-1 words. This probability can be computed using the formula:\n",
    "\n",
    "$$P(w_n|w_{1:n-1}) = \\frac{Count(w_{1:n-1}w_n)}{\\sum_{w}Count(w_{1:n-1}w)} = \\frac{Count(w_{1:n})}{Count(w_{1:n-1})}$$\n",
    "\n",
    "where $w_{1:n}$ are all the words in a sequence up the word $w_n$ at position $n$, and $w_{1:n-1}$ are all the words in a sequence before the word $w_n$ at position $n$.\n",
    "\n",
    "The n-gram model is a simplified approach to language modeling and is based on the Markov assumption, which assumes that the probability of a word only depends on a fixed number of preceding words. For example, if we only consider the $k=2$ words before the word $w_n$, then our probability formula becomes\n",
    "\n",
    "$$P(w_n|w_{1:n-1}) = P(w_n|w_{n-k:n-1})$$\n",
    "\n",
    "where $w_{n-k:n-1}$ are the $k$ words ahead of word $w_n$ in the sequence. While it has limitations in capturing long-range dependencies and context, n-gram models are computationally efficient and widely used in various natural language processing tasks such as speech recognition, machine translation, and text generation.\n",
    "\n",
    "This notebook covers the very basic idea behind n-gram language models. To this end, we implement the toy example from the lecture. The goal here is to show that training an n-Gram language model really just boils down to going through a text and counting the occurrences of n-grams for using Maximum Likelihood Estimation to compute the conditional probabilities. Of course, in practice, things can quickly become more complicated when (advanced) smoothing techniques are considered. But even then, the underlying requirement is counting the occurrences of n-gram. We use simple Add-k Smoothing to give an example for a smoothing technique -- compared to, e.g., Kneser-Ney Smoothing.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ba53cc52",
   "metadata": {},
   "source": [
    "## Setting up the Notebook\n",
    "\n",
    "### Import all Required Packages\n",
    "\n",
    "We'll use spaCy to handle the basics such as tokenization. Given the toy example containing only 3 sentences without punctuation marks, hyphenated words, abbreviations, or anything else that would make tokenization in any sense challenging, using spaCy is kind of overkill. However, this makes it easy to extend the corpus with your own sentences without worrying about the correct tokenization."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9244fee7",
   "metadata": {},
   "outputs": [],
   "source": [
    "import spacy\n",
    "nlp = spacy.load(\"en_core_web_sm\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e729d477",
   "metadata": {},
   "source": [
    "NLTK comes with some convenient methods to generate bigrams and trigrams which can also handle the padding, i.e., the adding of start-of-sentence and end-of-sentence tokens."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "495634b7",
   "metadata": {},
   "outputs": [],
   "source": [
    "from nltk.util import trigrams, bigrams\n",
    "from collections import defaultdict"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "085e7036-e8e5-44fe-8a3b-b9d425fcf8da",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0e9a0e7f",
   "metadata": {},
   "source": [
    "## Training the Language Model\n",
    "\n",
    "Training a n-gram language model is all about keeping counts of all n-grams found in a text. Here, we do this on a sentence-by-sentence basis. The method `process_sentence` below takes a sentence `s` and the current n-gram counts, goes through all n-grams in the sentence, and updates the n-gram counts accordingly. We also keep track of the vocabulary as we need the size of the vocabulary for smoothing.\n",
    "\n",
    "Note that we use a `defaultdict` instead of a standard dictionary here. This is purely for convenience, since we don't need to check if a key (i.e., a n-gram) is already present in the dictionary before updating the count. This just saves a couple of lines of code. We also only consider bigram and trigram language models. Again, this is purely to make the code as compact and easy to read as possible -- this is not a principle limitation!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "23ec87da",
   "metadata": {},
   "outputs": [],
   "source": [
    "def process_sentence(s, ngram_counts, vocabulary, ngram_size=2):\n",
    "    # Let spaCy handle the tokenization\n",
    "    doc = nlp(s)\n",
    "    # Get the individual text tokens\n",
    "    tokens = [ t.text for t in doc]\n",
    "    \n",
    "    # Update vocabulary\n",
    "    vocabulary.update(set(tokens))\n",
    "    \n",
    "    # Since we want to keep the simple here, we let NLTK to the generation of all ngram incl. the padding\n",
    "    # However, NLTK does this out of the box only for bigrams and trigrams, so let's limit ourselves here\n",
    "    if ngram_size == 2:\n",
    "        ngrams = bigrams\n",
    "    elif ngram_size == 3:\n",
    "        ngrams = trigrams\n",
    "    else:\n",
    "        raise Exception('Unsupported ngram size: either 2 or 3')\n",
    "    \n",
    "    # Now we can generate all ngrams and update our dictionary with all the counters\n",
    "    # We need the counts for the whole ngram and the context (ngram without the last word)\n",
    "    for ngram in ngrams(tokens, pad_left=True, pad_right=True, left_pad_symbol='<s>', right_pad_symbol='</s>'):\n",
    "        context = ngram[:-1]\n",
    "        ngram_counts[context] += 1\n",
    "        ngram_counts[ngram] += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5133f78c",
   "metadata": {},
   "source": [
    "Now we're ready to go to train the language model. We use the very small toy corpus from the lecture:\n",
    "\n",
    "```\n",
    "I am Sam\n",
    "Sam I am\n",
    "I do not like green eggs and ham\n",
    "```\n",
    "\n",
    "which is stored in the file `'data/toy-example-data.txt`. Feel free to modify and/or extend this corpus with sentences of your own. The only requirement is that each sentence must be in its own line in the file. Otherwise the following code would need a little bit of tweaking\n",
    "\n",
    "So let's just read the file and go through all the sentences and use method `process_sentence` to update our n-gram counts which are stored in `ngram_counts`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7d1a039b",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Initialize n-gram counts; using a defaultdict, the default count for missing keys/ngrams is 0\n",
    "ngram_counts = defaultdict(int)\n",
    "vocabulary = set()\n",
    "\n",
    "ngram_size = 2\n",
    "#ngram_size = 3\n",
    "\n",
    "with open('data/corpora/toy-example-data.txt', 'r') as file:\n",
    "    # Loop over each line in the file (1 line = 1 sentence)\n",
    "    for sentence in file.read().split('\\n'):\n",
    "        # Update n-gram counts using our auxiliary method\n",
    "        process_sentence(sentence, ngram_counts, vocabulary, ngram_size=ngram_size)\n",
    "\n",
    "# Display the final n-gram counts\n",
    "ngram_counts"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "db9b1f43-4a71-4bed-a504-02d765ad0310",
   "metadata": {},
   "source": [
    "Now we have the counts for all n-grams of size `ngram_size` and `ngram_size-1`, which is all we need to calculate the probabilities. In the case of a bigram language, a basic sanity check for the output above is that we see the unigram `(<s>)` 3 times since we have 3 sentences in out toy dataset. For a trigram language model, we should of course see the bigram `(<s>, <s>)` 3 times.\n",
    "\n",
    "For the smoothing, we also need the size of the vocabulary. Since we have the vocabulary already, this is a trivial step:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7b4a4cc6",
   "metadata": {},
   "outputs": [],
   "source": [
    "V = len(vocabulary)\n",
    "\n",
    "print(\"Numner of n-grams: {}\".format(len(ngram_counts)))\n",
    "print(\"Size of vocabulary: {}\".format(V))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3479fd97-7ccc-46df-934f-1d33ff9347b5",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dbb438f0",
   "metadata": {},
   "source": [
    "## Calculating Probabilities\n",
    "\n",
    "With all the n-gram counts, we can now compute the conditional probabilities using Maximum Likelihood Estimation as defined in the lecture. We also saw that Add-k Smoothing was a very simple extension. The method `calc_prob` below computes the probability of an n-gram; the Add-k Smoothing is optional."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4c874b59",
   "metadata": {},
   "outputs": [],
   "source": [
    "def calc_prob(ngram, ngram_counts, k=0, V=0):\n",
    "    # Convert the n-gram from a list to a tuples so we can use it as a key for our n-gram counts dictionary\n",
    "    ngram = tuple(ngram)\n",
    "    # Get the context, i.e., the n-gram without the last word\n",
    "    context = ngram[:-1]\n",
    "    # Calculate and return the probability using Maximum Likelihood Estimation\n",
    "    # We wrap the calculation in a TRY-CATCH block to handle divisions by zero if the context count is 0\n",
    "    try:\n",
    "        return (ngram_counts[ngram] + k) / (ngram_counts[context] + k*V)\n",
    "    except Exception as e:\n",
    "        return 0.0"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2b9cd9bf",
   "metadata": {},
   "source": [
    "### Bigram Examples\n",
    "\n",
    "Let's first calculate the bigram probabilities we used in the lecture. Note that these examples only work if you trained the language model with bigrams. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b6415746",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(calc_prob(['<s>', 'I'], ngram_counts))    \n",
    "print(calc_prob(['I', 'am'], ngram_counts))\n",
    "print(calc_prob(['am', 'Sam'], ngram_counts))\n",
    "print(calc_prob(['Sam', '</s>'], ngram_counts))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e672f73c",
   "metadata": {},
   "source": [
    "We can also compute the probabilities using Add-k Smoothing (e.g., Laplace Smoothing with $k=1$). The method `calc_prob` is ready for that."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "489e2029",
   "metadata": {},
   "outputs": [],
   "source": [
    "k = 1\n",
    "\n",
    "print(calc_prob(['<s>', 'I'], ngram_counts, k=k, V=V))    \n",
    "print(calc_prob(['I', 'am'], ngram_counts, k=k, V=V))\n",
    "print(calc_prob(['am', 'Sam'], ngram_counts, k=k, V=V))\n",
    "print(calc_prob(['Sam', '</s>'], ngram_counts, k=k, V=V))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3dff12fe",
   "metadata": {},
   "source": [
    "You can see how the probabilities drop when using smoothing as we move probability mass from n-grams with non-zero counts to all n-grams with zero counts. The smaller you make k, the less probability mass is moved; try $k=0.1$ to see the difference."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6711c0cb",
   "metadata": {},
   "source": [
    "### Trigram Examples\n",
    "\n",
    "If you train the language model using trigrams, you can check out the example below. The code cell still works after training a bigram model, but the probabilities will of course be 0 (at least without smoothing)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9c156999",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(calc_prob(['<s>', 'I', 'am'], ngram_counts))    \n",
    "print(calc_prob(['I', 'am', 'Sam'], ngram_counts))\n",
    "print(calc_prob(['<s>', 'Sam', 'I'], ngram_counts))\n",
    "print(calc_prob(['am', 'Sam', '</s>'], ngram_counts))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a66bfd45",
   "metadata": {},
   "source": [
    "And again, the same with smoothing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6f0b8db9",
   "metadata": {},
   "outputs": [],
   "source": [
    "k = 0.1\n",
    "\n",
    "print(calc_prob(['<s>', 'I', 'am'], ngram_counts, k=k, V=V))    \n",
    "print(calc_prob(['I', 'am', 'Sam'], ngram_counts, k=k, V=V))\n",
    "print(calc_prob(['<s>', 'Sam', 'I'], ngram_counts, k=k, V=V))\n",
    "print(calc_prob(['am', 'Sam', '</s>'], ngram_counts, k=k, V=V))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bae4cd5c-3c5a-4b23-a149-c6151adf6440",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9bb3c5ef",
   "metadata": {},
   "source": [
    "## Summary\n",
    "\n",
    "The basic idea behind training a n-gram language model is indeed quite straightforward: just count the occurrences of all n-grams. Of course, here, we purposefully ignored all challenges that come when training a language model over a very large corpus. Most importantly, the number of unique n-grams quickly increases, even exponentially w.r.t. the size of the n-grams.\n",
    "\n",
    "Still, basically all changes needed to the code above would address this challenge of handling a very large text corpus. The basic algorithm of going through the corpus and keeping track of all n-gram counts would remain exactly the same. Please keep in mind, however, that the code used in this notebook focuses on simplicity and understanding, and not on performance!\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3c95f7e8",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "cs5246",
   "language": "python",
   "name": "cs5246"
  },
  "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.9.15"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}