1-foundations/Section 3.2 - n-Gram Language Models (advanced).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "15a27e2f-9058-498d-b1e6-1ff4c405230d",
   "metadata": {},
   "source": [
    "<img src='data/images/section-notebook-header.png' />"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c8ab901a",
   "metadata": {},
   "source": [
    "# Lecture 03 - n-Gram Language Models (advanced)\n",
    "\n",
    "Having a notion of the probability of a sequence or sentence does no only allow to evaluate which of two sentences is more likely, but also predict the most likely word given a current sentence. In other words, we can use n-gram language models for **text generation**. Basic n-gram language models can be used for text generation by leveraging the probabilities of word sequences to generate coherent and contextually relevant text. Here's a general approach for using basic n-gram language models for text generation:\n",
    "\n",
    "* **Training the model:** Start by training the n-gram language model on a large corpus of text. The corpus should be representative of the type of text you want to generate. The model will estimate the probabilities of different n-grams based on the training data.\n",
    "\n",
    "* **Selecting the order (n):** Decide on the order of the n-grams you want to use for text generation. A higher value of n captures more context but can suffer from data sparsity, so it's a trade-off. Common values for n are 1 (unigram), 2 (bigram), or 3 (trigram), but you can experiment with different orders.\n",
    "\n",
    "* **Generating initial context:** Start the text generation process by providing an initial context, which can be a single word or a sequence of words. This context will serve as the starting point for generating the subsequent words.\n",
    "\n",
    "* **Generating the next word:** Based on the provided context, retrieve the n-1 gram that matches the preceding words. Use the n-gram language model to calculate the probability of each possible next word given the context.\n",
    "\n",
    "* **Sampling the next word:** Use the probabilities of the candidate words to make a decision on the next word. You can use techniques such as greedy sampling (selecting the word with the highest probability) or stochastic sampling (sampling a word based on its probability distribution).\n",
    "\n",
    "* **Updating the context:** Append the selected word to the context, shifting the window by one word. If necessary, truncate the context to match the desired order of n-grams.\n",
    "\n",
    "* **Repeat the process:** Repeat steps 4-6 to generate the subsequent words until you reach the desired length or generate a termination condition (e.g., a specific end-of-sentence token).\n",
    "\n",
    "* **Post-processing:** Depending on the application and desired output, you may need to perform post-processing steps such as capitalization, punctuation, or formatting to make the generated text more coherent and readable.\n",
    "\n",
    "It's important to note that basic n-gram language models may produce grammatically correct but not necessarily semantically accurate or contextually rich text. They lack long-range dependencies and global context awareness. To overcome these limitations, more advanced language models, such as recurrent neural network models or transformer models like GPT, are often used for text generation tasks."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ba53cc52",
   "metadata": {},
   "source": [
    "## Setting up the Notebook\n",
    "\n",
    "### Import all Required Packages\n",
    "\n",
    "We need `spaCy` for preparing our corpus and `requests` to download the text documents that serve as corpora to train our language model."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9244fee7",
   "metadata": {},
   "outputs": [],
   "source": [
    "import spacy\n",
    "nlp = spacy.load(\"en_core_web_sm\")\n",
    "\n",
    "import requests"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "50b5981c-1343-4984-bac1-dcec5c41f1f1",
   "metadata": {},
   "source": [
    "Lastly, we need to import the implementation of our n-gram language model, which is provided as its own class in a separate `.py` script file. This not only keeps the notebook cleaner, but also makes it easier for you to reuse the code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d6e894ca-7fbc-4b2e-832b-ca17e8bbdc55",
   "metadata": {},
   "outputs": [],
   "source": [
    "from src.ngramlm import NgramLanguageModel"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e2f1da8e-0c93-4b63-bd71-2f6baccdeb73",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5133f78c",
   "metadata": {},
   "source": [
    "## Creating the Language Model Class\n",
    "\n",
    "The core component of this notebook is of course the language model. Here, we warp the implementation into a Python class. This makes the implementation a bit more compact and tidy. Compared to the basic notebook about language models, the following code needs some more complexity. However, the core requirement is still to go through a corpora and keep track of the n-gram counts that allows us the conditional probabilities of the n-grams, i.e., the probability of a word given a context.\n",
    "\n",
    "While the code in the `.py` file contains comments, let's address some of the basic components:\n",
    "\n",
    "* The class variable `ngram_counter` contains the counts for each existing n-gram. This is the same approach as in the basic notebook. Again, we use a `defaultdict` to make life a tad easier. As we do not have to worry about non-existing keys (i.e., n-grams) when updating the counts. The keys of the dictionaries are n-grams represented as tuples as tuples, compared to lists, are hashable and as such can be used as dictionary keys (e.g., `ngram_counter[('i', 'saw', 'that')] = 14`).\n",
    "\n",
    "* The class variable `self.context` contains for each context the list of words/tokens that followed a context at least once. This list of words will represent our candidates when we generate new words given a context. The intuition is that we want to generate only words that we have seen at least once after the given context.\n",
    "\n",
    "* The class method `preprocess_sentence` does some cleaning, mainly removing non-ascii characters and `\\s` characters (e.g., tabs, line breaks) and replacing them with a single space character. The method also uses spaCy to tokenize a sentence and return the list of tokens as result.\n",
    "\n",
    "* The class method `get_ngrams` takes a list of tokens and generates all n-grams of the user-specified size (specified in the constructor). It also first pads the list of tokens with the start-of-sequence and end-of-sequence tokens. The amount of padding, of course, depends on the size of the ngrams.\n",
    "\n",
    "* The class method `update` takes a sentence as input, preprocesses it and goes through all n-grams and updates the respective counts in `ngram_counter`. Note that we ignore sentences if its length is smaller than the n-gram size. In short, the method `update` is the main method we use for training our Language Model one sentence at a time.\n",
    "\n",
    "* The class method `calc_prob` computes the conditional probability of a word/token given a context; we've already seen this in the basic notebook. Note that we don't need any smoothing as we generate new words and only pick words that we have seen at least once for a given context. We therefore do not have to deal with zero probabilities here.\n",
    "\n",
    "* The class method `random_token` picks a random word/token given a context. As already mentioned, we only consider words/tokens we have seen at least once following the given context. From these candidate words/tokens, we pick randomly but not uniformly randomly. We utilize the probabilities of each candidate word/token given the index to favor words we have seen more frequently following the context.\n",
    "\n",
    "* The class method `generate_text` does the actual generation of a sentence and gives an optional list of start/seed tokens. In its core, the method generates a new word in each iteration until (a) the end-of-sentence token is generated or (b) the sentence has reached the specified maximum length. This is usually done as failsafe to avoid cases where the end-of-sentence token is never generated.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "75aac7e0-ab59-4b4a-a35a-0ed2371787da",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "86b9eae5",
   "metadata": {},
   "source": [
    "## Prepare Text Corpus\n",
    "\n",
    "To train a language model, we need a text corpus. Ideally, this corpus should be very large and representative to cover a wide range of n-grams. In this notebook, however, we have to keep it simple. We therefore use publicly available books that can be downloaded from [Project Gutenberg](https://www.gutenberg.org/). Most books are available as plain text files for us to train a model.\n",
    "\n",
    "### Download Books from Project Gutenberg\n",
    "\n",
    "The following code cell downloads a book's plain text file to store it locally in the `data/` folder . Feel free to browse the Project Gutenberg website to find the links to your books of choice. The example below is the Sherlock Holmes novel \"The Hound of the Baskervilles\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4c874b59",
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "\n",
    "url = 'https://www.gutenberg.org/files/2852/2852-0.txt' # The Hound of the Baskervilles (Sir Arthur Conan Doyle)\n",
    "\n",
    "# Download the file using the given URL\n",
    "r = requests.get(url, allow_redirects=True)\n",
    "\n",
    "# Specify where to save the file\n",
    "file_name = 'data/corpora/{}'.format(url.split('/')[-1])\n",
    "\n",
    "# Save the file locally\n",
    "open(file_name, 'wb').write(r.content)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eda06bad-03e2-4781-986e-8af7c18c4cfa",
   "metadata": {},
   "source": [
    "The output reflect the size of the file in bytes."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8d858d99",
   "metadata": {},
   "source": [
    "### Analyze File Using spaCy\n",
    "\n",
    "The text files for books from Project Gutenberg are not conveniently structured so that each line represents a sentence. We therefore need a way to first split the document into sentences. The most convenient here is to simply use spaCy.\n",
    "\n",
    "Note that this is not a great way to do it as it does not scale to really large corpora. For example, it would be impossible to give a large Wikipedia dump to spaCy. So in practice, a large corpus would first need to be split into reasonably sized chunks. However, spaCy seems to handle at least \"The Hound of the Baskervilles\" quite well.\n",
    "\n",
    "**Important:** If the code cell below crashes for you, you may want to try a short(er) book first."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a9efe041",
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time \n",
    "\n",
    "# Read text file into a string\n",
    "text = open(file_name).read()\n",
    "\n",
    "# Set the max. length of a string for spaCy to the length of the document\n",
    "nlp.max_length = len(text)\n",
    "\n",
    "# Analyze document (includes splitting the docment into sentences)\n",
    "doc = nlp(text)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cc8078a8-078b-4b27-bf15-a2b8ec27f140",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e34d6dcc",
   "metadata": {},
   "source": [
    "## Training the Language Model\n",
    "\n",
    "With the code we have, training a language model is easy. We only need to decide on the size of the n-grams. You're of course encouraged to try different n-gram sizes and see how it affects the generated sentences, but also the number of n-grams."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8f818b2f",
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "\n",
    "#ngram_size = 2\n",
    "#ngram_size = 3\n",
    "ngram_size = 4\n",
    "#ngram_size = 5\n",
    "\n",
    "model = NgramLanguageModel(ngram_size)\n",
    "\n",
    "for s in doc.sents:\n",
    "    model.update(s.text)\n",
    "\n",
    "print(\"Number of n-grams: {}\".format(len(model.ngram_counter)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d71a9d76-b63f-4f42-821a-b5127f8d5b7f",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "306769f2",
   "metadata": {},
   "source": [
    "## Generating Sentences\n",
    "\n",
    "After the training, the model is ready to generate new sentences utilizing the probabilities of the n-grams based on the now available n-gram counts. As we don't use smoothing, the only requirement is that the start/seed words represented by `start_context` (more specifically, the last `(self.n - 1)` in `start_context`) are an existing n-gram.\n",
    "\n",
    "Since we pick the next words (kind of) randomly, executing the same example multiple times will generally yield different sentences. Try different start/seed words and see the generated sentences using multiple runs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "eae75361",
   "metadata": {},
   "outputs": [],
   "source": [
    "# This will not work for \"The hound of the Baskervilles\" as no sentence in there starts with \"I love ...\"\n",
    "#print(model.generate_text(50, start_context=['i', 'love']))\n",
    "\n",
    "# These should all work for \"The hound of the Baskervilles\"\n",
    "print(model.generate_text(50, start_context=['i', 'saw']))\n",
    "print(model.generate_text(50, start_context=['he', 'said', 'that']))\n",
    "print(model.generate_text(50, start_context=['the', 'train']))\n",
    "print(model.generate_text(50, start_context=['sherlock', 'holmes']))\n",
    "print(model.generate_text(50, start_context=['the', 'day']))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "861b3e5a",
   "metadata": {},
   "source": [
    "#### Some Observations\n",
    "\n",
    "If you use \"The Hound of the Baskervilles\", you should make some basic observations:\n",
    "\n",
    "* For smaller n-grams (e.g., of size 2 or 3) the sentences are more garbled. This is of course no surprise, give the very small context we use to generate the next word\n",
    "* Increasing the size of the n-grams will generally yield more coherent sentences. Again, this is expected as we increase the context for predicting the next word.\n",
    "* Very quickly, when we increase the size of the n-grams to 5 or larger, the generated sentences are mostly sentences that can be directly found in the book. This is because our corpus is overall very small making most n-grams essentially unique. This also means that the list of candidate words for a context from which we pick the next words is of size 1 most of the time, making the sentence generation more or less deterministic.\n",
    "* An n-gram size of 4 seems to be the sweet spot here. The generated sentences are rather coherent, and there is still some randomness to yield different sentences when performing multiple runs using the same start/seed words.\n",
    "\n",
    "Of course, if you use a different corpus, these observations might (slightly) differ."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c7749ab4-c452-4472-bb03-5e9764a0418a",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "856a4501",
   "metadata": {},
   "source": [
    "## Summary\n",
    "\n",
    "A simple n-gram language model is a basic implementation of the n-gram concept in language modeling. It estimates the probability of a word based on the preceding n-1 words by counting the occurrences of n-grams in a training corpus. Here's a brief summary of simple n-gram language models:\n",
    "\n",
    "* **Training:** A simple n-gram model requires a training corpus, which is a collection of text used to estimate the probabilities. The corpus is tokenized into words or other units, and n-grams are created by sliding a window of n words over the text.\n",
    "\n",
    "* **Counting n-grams:** The model counts the occurrences of each n-gram in the training corpus. For example, in the sentence \"I love to play soccer,\" the bigram \"I love\" would have a count of 1, and the trigram \"love to play\" would also have a count of 1.\n",
    "\n",
    "* **Computing probabilities:** The model calculates the probability of encountering a particular word given the preceding n-1 words. This is done by dividing the count of a specific n-gram by the count of the n-1 gram. For example, to estimate the probability of the word \"play\" given the previous two words \"love to,\" the model divides the count of the trigram \"love to play\" by the count of the bigram \"love to.\"\n",
    "\n",
    "* **Prediction:** Given a sequence of words, the model can predict the next word by selecting the word with the highest probability based on the n-grams. It looks for the n-1 gram that matches the preceding words and selects the most probable next word.\n",
    "\n",
    "* **Limitations:** Simple n-gram models have limitations in capturing long-range dependencies and context. They assume that the probability of a word depends only on a fixed number of preceding words, neglecting global context. Additionally, n-grams with higher values of n may suffer from data sparsity, where some n-grams have zero counts in the training corpus.\n",
    "\n",
    "* **Applications:** Simple n-gram language models are computationally efficient and widely used in various natural language processing tasks. They are commonly employed in applications such as text generation, spelling correction, auto-completion, and machine translation.\n",
    "\n",
    "While simple n-gram language models have their limitations, they serve as a fundamental building block in language modeling and provide a starting point for more advanced models that aim to capture more complex linguistic patterns and dependencies."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "39dfdc28",
   "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
}