notebook_05_ngram_markov_assumption.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/julurisaichandu/nlp/blob/main/notebook_05_ngram_markov_assumption.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "yCxplrXRH8D8"
      },
      "source": [
        "Notebook 5: N-gram Language Models\n",
        "===============\n",
        "\n",
        "CS 6120 Natural Language Processing, Amir\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vgU3i7vkH8ER"
      },
      "source": [
        "Saichandu Juluri"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1EkFy3YYH8EV"
      },
      "source": [
        "Saving notebooks as pdfs\n",
        "----------\n",
        "\n",
        "Feel free to add cells to this notebook as you wish. Make sure to leave **code that you've written** and any **answers to questions** that you've written in your notebook. Turn in your notebook as a pdf at the end of lecture's day.\n",
        "\n",
        "\n",
        "To convert your notebook to a pdf for turn in, you'll do the following:\n",
        "1. Kernel -> Restart & Run All (clear your kernel's memory and run all cells)\n",
        "2. File -> Download As -> .html -> open in a browser -> print to pdf\n",
        "\n",
        "(The download as pdf option doesn't preserve formatting and output as nicely as taking the step \"through\" html, but will do if the above doesn't work for you.)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "G3Y-lTruH8Ed"
      },
      "source": [
        "Task 1: Implement an N-gram Language Model\n",
        "-------\n",
        "\n",
        "Recall that a language model estimates the probability of a sentence as\n",
        "\n",
        "$P(w_1, \\ldots, w_N) = \\prod_i^N P(w_i | w_{1},\\ldots,w_{i-1})$\n",
        "\n",
        "N-gram Language Models approximate the conditional probabilities using a Markov Assumption\n",
        "\n",
        "$P(w_i| w_1, \\ldots, w_{i-1}) \\approx P(w_i | w_{i-n+1}, \\ldots, w_{i-1})$\n",
        "\n",
        "e.g., for bi-grams we get\n",
        "\n",
        "$P(w_i| w_1, \\ldots, w_{i-1}) \\approx P(w_i | w_{i-1})$\n",
        "\n",
        "Training entails estimating the n-gram probabilities\n",
        "\n",
        "$P(w_i | w_{i-n+1}, \\ldots, w_{i-1}) = \\frac{\\text{count}(w_{i-n+1}, \\ldots, w_{i-1}w_i)}{\\text{count}(w_{i-n+1}, \\ldots, w_{i-1})}$\n",
        "\n",
        "for bi-grams we get\n",
        "\n",
        "$P(w_i|w_{i-1}) =\\frac{\\text{count}(w_{i-1}w_i)}{\\text{count}(w_{i-1})}$\n",
        "\n",
        "Note that for unigrams we compute the unconditional word probabilities\n",
        "\n",
        "$P(w_i) =\\frac{\\text{count}(w_i)}{\\sum_{j \\in V}\\text{count}(w_{j})}$\n",
        "\n",
        "We may also want to use Laplace Smoothing (like we did for Naive Bayes training)\n",
        "\n",
        "\n",
        "We measure model performance by calculating perplexity on a test set\n",
        "\n",
        "$PP(w_1, \\ldots, w_N) = P(w_1, \\ldots, w_N)^{-1/N}$\n",
        "\n",
        "\n",
        "<!-- To make this calculation more stable we can operate in log space\n",
        "\n",
        "$\\hat{y} = \\arg\\max_{y \\in \\{0, 1\\}} \\log P(y) + \\sum_{i=1}^{n} \\log P(x_i|y)$\n",
        "\n",
        "Training entails estimating:\n",
        "\n",
        "1. class priors\n",
        "\n",
        "$P(y) = \\frac{N_y}{N}$\n",
        "where $N_y$ is the number of documents with class $y$ and $N$ is the total number of documents\n",
        "\n",
        "\n",
        "2. class conditional word probabilities\n",
        "\n",
        "$P(x_i|y) = \\frac{\\text{count}(x_i,y)}{\\sum_{x \\in V} \\text{count}(x,y)}$\n",
        "\n",
        "\n",
        "Also recall that we should use smoothing when calculating the above probabilities\n",
        "\n",
        "$P(x_i|y) = \\frac{\\text{count}(x_i,y) + \\alpha}{\\sum_{x \\in V} \\text{count}(x,y)+ \\alpha|V|}$ -->\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "7gJMicM4H8Ei"
      },
      "outputs": [],
      "source": [
        "from collections import Counter\n",
        "import numpy as np\n",
        "import matplotlib.pyplot as plt\n",
        "import math\n",
        "from typing import List, Text"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "71p5gAhSH8Ep"
      },
      "outputs": [],
      "source": [
        "def create_ngrams(tokens: List[Text], n: int):\n",
        "  \"\"\"\n",
        "    Take a sequence of tokens and return a list of n-grams\n",
        "  \"\"\"\n",
        "  ngrms_list = []\n",
        "  for i in range(len(tokens) - n + 1):\n",
        "      ngrms_list.append(tuple(tokens[i:i + n]))\n",
        "  return ngrms_list\n",
        "\n",
        "\n",
        "class NGRAM_LM:\n",
        "  unk = \"<UNK>\"\n",
        "  start_token = \"<s>\"\n",
        "  end_token = \"</s>\"\n",
        "\n",
        "  def __init__(self, n_gram: int, smoothing: bool):\n",
        "\n",
        "    #n-gram order\n",
        "    self.n = n_gram\n",
        "    #enable/disable Laplace smoothing\n",
        "    self.smoothing = smoothing\n",
        "    #counter for n-grams (i.e., the numerator to calculate n-gram probs)\n",
        "    self.n_grams = Counter()\n",
        "    #counter for n-1-grams (i.e., the denominator to calculate n-gram probs)\n",
        "    self.n_minus_one_grams = Counter()\n",
        "\n",
        "  def train(self, training_file_path: Text):\n",
        "    \"\"\"\n",
        "      Train the language model by accumulating counts of n-grams and n-1-grams\n",
        "      Note: *do not* include the pseudo-counts if smoothing is enabled (we will do this at inference time)\n",
        "    \"\"\"\n",
        "    with open(training_file_path, \"r\") as f:\n",
        "      # count the unigrams and keep track of all the words (we may need to replace some of these with unks)\n",
        "      unigrams = Counter()\n",
        "      all_tokens = []\n",
        "      for sentence in f:\n",
        "        words = sentence.split()\n",
        "        unigrams.update(words)\n",
        "        all_tokens += words\n",
        "\n",
        "      # replace singletons with UNK\n",
        "      unigrams = Counter([word if unigrams[word] > 1 else self.unk\n",
        "                          for word in all_tokens])\n",
        "\n",
        "      self.vocab = list(unigrams.keys())\n",
        "      self.token_counts = sum(unigrams.values())\n",
        "\n",
        "      # now collect our ngrams and n-1-gram counts\n",
        "      # Creating n-grams by replacing unknown words with UNK\n",
        "      ngrams = create_ngrams([word if unigrams[word] > 1 else self.unk\n",
        "                              for word in all_tokens], self.n)\n",
        "      self.n_grams.update(ngrams)\n",
        "\n",
        "      # Creating n-1-grams by replacing unknown words with UNK\n",
        "      n_minus_1_grams = create_ngrams([word if unigrams[word] > 1\n",
        "                                       else self.unk for\n",
        "                                       word in all_tokens], self.n - 1)\n",
        "      self.n_minus_one_grams.update(n_minus_1_grams)\n",
        "\n",
        "\n",
        "    print(\"Training n-gram:\", self.n)\n",
        "    print(\"vocab size:\", len(self.vocab))\n",
        "    print(\"Token Counts:\", self.token_counts)\n",
        "    print(\"N-gram Counts:\", sum(self.n_grams.values()))\n",
        "    print(\"Unique n-grams:\", len(self.n_grams))\n",
        "    print(\"n-1-grams Counts\", sum(self.n_minus_one_grams.values()))\n",
        "    print(\"Unique n-1-grams:\", len(self.n_minus_one_grams))\n",
        "    print(\"<UNK> Counts:\", unigrams[self.unk])\n",
        "    print()\n",
        "\n",
        "  def score(self, sentence: Text):\n",
        "    \"\"\"\n",
        "      Compute the probability of a sequence as a product of individual n-gram probabilities\n",
        "      (or sum of log probabilities)\n",
        "      We will use the counts that were accumulated during training to compute the individual n-gram probabilities\n",
        "      if smoothing is enabled we also need to add the pseudo-counts\n",
        "      Note that there are two cases: unigrams and n-grams (with n > 1)\n",
        "\n",
        "    \"\"\"\n",
        "    words = sentence.strip().split()\n",
        "    # making unknown words in vocab as UNK\n",
        "    words = [self.unk if not word in self.vocab else word for word in words]\n",
        "    # converting the list to ngrams\n",
        "    sent_ngrams = create_ngrams(words, self.n)\n",
        "    total_prob = 0\n",
        "    # for each n gram calc prob\n",
        "    for sent_ngram in sent_ngrams:\n",
        "      # if n=1, then the formula is as follows\n",
        "      if self.n == 1:\n",
        "            # Unigram\n",
        "            count = self.n_grams[sent_ngram]\n",
        "            # laplace smoothing\n",
        "            if self.smoothing:\n",
        "                prob = (count + 1) / (self.token_counts + len(self.vocab))\n",
        "            else:\n",
        "                prob = count / self.token_counts\n",
        "      else:\n",
        "          # n-gram\n",
        "          n_minusone_gram = sent_ngram[:-1]\n",
        "          count = self.n_grams[sent_ngram]\n",
        "          prev_count = self.n_minus_one_grams[n_minusone_gram]\n",
        "\n",
        "          if self.smoothing:\n",
        "              # Laplace smoothing\n",
        "              prob = (count + 1) / (prev_count + len(self.vocab))\n",
        "          else:\n",
        "              prob = count / prev_count if prev_count > 0 else 0\n",
        "\n",
        "      # taking prob only if its grater than 0 to avoid infinity value for log\n",
        "      if prob > 0:\n",
        "          total_prob += np.log(prob)\n",
        "\n",
        "    return total_prob\n",
        "\n",
        "\n",
        "  # TODO: implement\n",
        "  def perplexity(self, sentence: Text):\n",
        "    \"\"\"\n",
        "      Compute the perplexity of a sentence under the model\n",
        "    \"\"\"\n",
        "    return math.exp(-self.score(sentence)/len(sentence.strip().split()))\n",
        "\n",
        "\n",
        "\n",
        "  def generate(self):\n",
        "    \"\"\"\n",
        "      Generate a sentence using Shannon's method\n",
        "    \"\"\"\n",
        "    num_begin = self.n - 1 if self.n > 1 else 1\n",
        "    sent = [self.start_token for i in range(num_begin)]\n",
        "    curr = sent[len(sent) - 1]\n",
        "    if self.n == 1:\n",
        "      # remove the <s> from our vocab for unigrams\n",
        "      lookup = [word for word in self.vocab if word != self.start_token]\n",
        "      #remove counts of the start of sentence\n",
        "      token_counts = self.token_counts - self.n_grams[tuple([self.start_token])]\n",
        "      weights = [(self.n_grams[tuple([word])])/(token_counts) for word in lookup]\n",
        "\n",
        "    while curr != self.end_token:\n",
        "      if (self.n > 1):\n",
        "        # get the n - 1 previous words that we are sampling\n",
        "        previous = tuple(sent[len(sent) - (self.n - 1) : len(sent)])\n",
        "        previous_count = self.n_minus_one_grams[previous]\n",
        "\n",
        "        lookup = [choice for choice in self.n_grams if choice[:-1] == previous]\n",
        "        weights = [self.n_grams[choice] / previous_count for choice in lookup]\n",
        "\n",
        "      to_sample = np.arange(len(lookup))\n",
        "      next = lookup[np.random.choice(to_sample, p=weights)]\n",
        "      #avoid generating just start and end of sentence\n",
        "      if next == self.end_token and curr == self.start_token: continue\n",
        "\n",
        "      if self.n == 1:\n",
        "        sent.append(next)\n",
        "      else:\n",
        "        sent.append(next[-1])\n",
        "      curr = sent[-1]\n",
        "\n",
        "    return \" \".join(sent)\n",
        "\n",
        "\n",
        "def score_testfile(lm: NGRAM_LM, test_file_path: Text):\n",
        "  \"\"\"\n",
        "    Compute the probability score for a set of sentences on a test set\n",
        "    Prints the number of sentences, average probability and standard deviation\n",
        "  \"\"\"\n",
        "\n",
        "  with open(test_file_path, \"r\", encoding=\"utf8\") as f:\n",
        "      scores = [lm.score(s.strip()) for s in f.readlines()]\n",
        "\n",
        "  print(\"Number of sentences:\", len(scores))\n",
        "  print(\"Average score:\", np.average(scores))\n",
        "  print(\"Std deviation:\", np.std(scores))\n",
        "  print()\n",
        "\n",
        "\n",
        "def train_test_lm(n_gram: int, smooth: bool):\n",
        "  \"\"\"\n",
        "    Train and test an n-gram language mode\n",
        "  \"\"\"\n",
        "  #Paths\n",
        "  trainingFilePath = \"LM-training.txt\"\n",
        "  test_file_path = \"LM-test.txt\"\n",
        "  test_sentence = \"<s> sam i am and today I am walking away </s>\"\n",
        "\n",
        "  language_model = NGRAM_LM(n_gram, smooth)\n",
        "  language_model.train(trainingFilePath)\n",
        "\n",
        "  print(\"Score on test file\")\n",
        "  score_testfile(language_model, test_file_path)\n",
        "  print(\"Probability of test sentence: \", language_model.score(test_sentence))\n",
        "  print(\"Perplexity of test sentence \", language_model.perplexity(test_sentence))\n",
        "\n",
        "  return language_model\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ynQ92w5KH8Ew"
      },
      "source": [
        "Q1: Implement the `create_ngrams()` method which takes as input a string and an `n` parameter and returns a list of `n-grams`"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "3eWIrPijH8E1"
      },
      "outputs": [],
      "source": [
        "def create_ngrams(tokens: List[Text], n: int):\n",
        "  \"\"\"\n",
        "    Take a sequence of tokens and return a list of n-grams\n",
        "  \"\"\"\n",
        "  ngrms = []\n",
        "  for i in range(len(tokens) - n + 1):\n",
        "    ngrms.append(tuple(tokens[i:i+n]))\n",
        "  return ngrms"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "zfQAYdNvH8E5"
      },
      "source": [
        "Q2: Implement the `train()` method. We have already implemented code to: count unigram occurrences, replace singleton tokens with UNK, and induce the vocabulary. Now you need read the training data again and count the occurrence of n-grams and n-1-grams. The actual probabilities will be computed at inference time. Do not add the pseudo-counts for smoothing (this will be done when computing the actual probabilities)."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "2tJQfr0zH8E8"
      },
      "outputs": [],
      "source": [
        "def train(self, training_file_path: Text):\n",
        "    \"\"\"\n",
        "      Train the language model by accumulating counts of n-grams and n-1-grams\n",
        "      Note: *do not* include the pseudo-counts if smoothing is enabled (we will do this at inference time)\n",
        "    \"\"\"\n",
        "    with open(training_file_path, \"r\") as f:\n",
        "      # count the unigrams and keep track of all the words (we may need to replace some of these with unks)\n",
        "      unigrams = Counter()\n",
        "      all_tokens = []\n",
        "      for sentence in f:\n",
        "        words = sentence.split()\n",
        "        unigrams.update(words)\n",
        "        all_tokens += words\n",
        "\n",
        "      # replace singletons with UNK\n",
        "      unigrams = Counter([word if unigrams[word] > 1 else self.unk\n",
        "                          for word in all_tokens])\n",
        "\n",
        "      self.vocab = list(unigrams.keys())\n",
        "      self.token_counts = sum(unigrams.values())\n",
        "\n",
        "      # now collect our ngrams and n-1-gram counts\n",
        "      # Create n-grams\n",
        "      ngrams = create_ngrams([word if unigrams[word] > 1 else self.unk\n",
        "                              for word in all_tokens], self.n)\n",
        "      self.n_grams.update(ngrams)\n",
        "\n",
        "      # Create n-1-grams for normalization\n",
        "      n_minus_1_grams = create_ngrams([word if unigrams[word] > 1\n",
        "                                       else self.unk\n",
        "                                       for word in all_tokens], self.n - 1)\n",
        "      self.n_minus_one_grams.update(n_minus_1_grams)\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vRH-De7iH8E9"
      },
      "source": [
        "Q3: Implement the `score()` method which takes a sentence as input and calculates its probability with and without Laplace smoothing. Use the counts from the training step to calculate the individual n-gram probabilities (`self.token_counts` has the sum of the counts of all tokens in the corpus).\n",
        "\n",
        "Q3.1: Implement the `perplexity()` method (you can use the probabilities from the score method)\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "X92_aPYoH8E-"
      },
      "outputs": [],
      "source": [
        "def score(self, sentence: Text):\n",
        "  \"\"\"\n",
        "    Compute the probability of a sequence as a product of individual n-gram probabilities\n",
        "    (or sum of log probabilities)\n",
        "    We will use the counts that were accumulated during training to compute the individual n-gram probabilities\n",
        "    if smoothing is enabled we also need to add the pseudo-counts\n",
        "    Note that there are two cases: unigrams and n-grams (with n > 1)\n",
        "\n",
        "  \"\"\"\n",
        "  words = sentence.strip().split()\n",
        "  # making unknown words in vocab as UNK\n",
        "  words = [self.unk if not word in self.vocab else word for word in words]\n",
        "  # converting the list to ngrams\n",
        "  sent_ngrams = create_ngrams(words, self.n)\n",
        "  total_prob = 0\n",
        "  # for each n gram calc prob\n",
        "  for sent_ngram in sent_ngrams:\n",
        "    # if n=1, then the formula is as follows\n",
        "    if self.n == 1:\n",
        "          # Unigram\n",
        "          count = self.n_grams[sent_ngram]\n",
        "          # laplace smoothing\n",
        "          if self.smoothing:\n",
        "              prob = (count + 1) / (self.token_counts + len(self.vocab))\n",
        "          else:\n",
        "              prob = count / self.token_counts\n",
        "    else:\n",
        "        # n-gram\n",
        "        n_minusone_gram = sent_ngram[:-1]\n",
        "        count = self.n_grams[sent_ngram]\n",
        "        prev_count = self.n_minus_one_grams[n_minusone_gram]\n",
        "\n",
        "        if self.smoothing:\n",
        "            # Laplace smoothing\n",
        "            prob = (count + 1) / (prev_count + len(self.vocab))\n",
        "        else:\n",
        "            prob = count / prev_count if prev_count > 0 else 0\n",
        "\n",
        "    # taking prob only if its grater than 0 to avoid infinity value for log\n",
        "    if prob > 0:\n",
        "        total_prob += np.log(prob)\n",
        "\n",
        "  return total_prob\n",
        "\n",
        "\n",
        "def perplexity(self, sentence: Text):\n",
        "  \"\"\"\n",
        "    Compute the perplexity of a sentence under the model\n",
        "  \"\"\"\n",
        "  len_of_sentence = len(sentence.strip().split())+2 # start and end token\n",
        "  return math.exp(-self.score(sentence)/len(sentence.strip().split()))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "2rKKVynNH8E_"
      },
      "source": [
        "Q4: Use the `train_test_lm()` method to evaluate a unigram and a bigram LM (with and without smoothing). What do you observe?"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "XSv9o5qqH8FB",
        "outputId": "d130ece4-1fcb-41de-c3c2-e82e8017a45b"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "\n",
            "unigram without smoothing\n",
            "Training n-gram: 1\n",
            "vocab size: 923\n",
            "Token Counts: 56696\n",
            "N-gram Counts: 56696\n",
            "Unique n-grams: 923\n",
            "n-1-grams Counts 56697\n",
            "Unique n-1-grams: 1\n",
            "<UNK> Counts: 478\n",
            "\n",
            "Score on test file\n",
            "Number of sentences: 101\n",
            "Average score: -37.21092847483953\n",
            "Std deviation: 19.3752306064226\n",
            "\n",
            "Probability of test sentence:  -57.634641729807186\n",
            "Perplexity of test sentence  188.57822065999315\n",
            "\n",
            "bigram without smoothing\n",
            "Training n-gram: 2\n",
            "vocab size: 923\n",
            "Token Counts: 56696\n",
            "N-gram Counts: 56695\n",
            "Unique n-grams: 8289\n",
            "n-1-grams Counts 56696\n",
            "Unique n-1-grams: 923\n",
            "<UNK> Counts: 478\n",
            "\n",
            "Score on test file\n",
            "Number of sentences: 101\n",
            "Average score: -15.347592920219412\n",
            "Std deviation: 7.58723791411062\n",
            "\n",
            "Probability of test sentence:  -15.150356455236562\n",
            "Perplexity of test sentence  3.9642042139962927\n",
            "\n",
            "unigram with smoothing\n",
            "Training n-gram: 1\n",
            "vocab size: 923\n",
            "Token Counts: 56696\n",
            "N-gram Counts: 56696\n",
            "Unique n-grams: 923\n",
            "n-1-grams Counts 56697\n",
            "Unique n-1-grams: 1\n",
            "<UNK> Counts: 478\n",
            "\n",
            "Score on test file\n",
            "Number of sentences: 101\n",
            "Average score: -37.224670831183495\n",
            "Std deviation: 19.341354486989882\n",
            "\n",
            "Probability of test sentence:  -57.69339945881221\n",
            "Perplexity of test sentence  189.5882274255299\n",
            "\n",
            "bigram with smoothing\n",
            "Training n-gram: 2\n",
            "vocab size: 923\n",
            "Token Counts: 56696\n",
            "N-gram Counts: 56695\n",
            "Unique n-grams: 8289\n",
            "n-1-grams Counts 56696\n",
            "Unique n-1-grams: 923\n",
            "<UNK> Counts: 478\n",
            "\n",
            "Score on test file\n",
            "Number of sentences: 101\n",
            "Average score: -28.046380999732836\n",
            "Std deviation: 16.418342594431618\n",
            "\n",
            "Probability of test sentence:  -61.0781276180953\n",
            "Perplexity of test sentence  257.8961684863527\n"
          ]
        }
      ],
      "source": [
        "print('\\nunigram without smoothing')\n",
        "unigram_lm = train_test_lm(1, False)\n",
        "print('\\nbigram without smoothing')\n",
        "bigram_lm = train_test_lm(2, False)\n",
        "\n",
        "print('\\nunigram with smoothing')\n",
        "unigram_lm_smooth = train_test_lm(1, True)\n",
        "print('\\nbigram with smoothing')\n",
        "bigram_lm_smooth = train_test_lm(2, True)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "xAkWZIghH8FC"
      },
      "source": [
        "Q5: Use the `generate()` method to generate samples from your language models. Compare the samples from a unigram and bigram language models. What do you notice?\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "IncYAzEUH8FD",
        "outputId": "fe828a16-b82f-4e20-ed24-4291b37909e7"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Generate sentences:\n",
            "Bigrams without smoothing\n",
            "['<s> tell me a distance </s>', '<s> is your database </s>', \"<s> what's the list again </s>\", '<s> i can you have lunch </s>', '<s> where can you to eat dinner </s>']\n",
            "Bigrams with smoothing\n",
            "['<s> kosher </s>', \"<s> could you show me about greek restaurants around icsi can you know about lunch should be at bucci's menu of southern style restaurant </s>\", '<s> ten dollars </s>', '<s> start over please </s>', \"<s> show me that right can be at any type of let's try again </s>\"]\n",
            "unigrams without smoothing\n",
            "['<s> want the on restaurant reasonably want i lunch should help like show um as i some within </s>', '<s> is </s>', \"<s> twenty oh actually house okay any the is doesn't i food try takes you you </s>\", '<s> out desserts start </s>', '<s> how house what be something </s>']\n",
            "unigrams with smoothing\n",
            "['<s> restaurant list the japanese it very </s>', \"<s> mcdonald's like okay return lunch i over give about i </s>\", '<s> are californian again </s>', '<s> ten i walking go to a casa-de-eva italian fifteen </s>', \"<s> american on of there i'd avenue no </s>\"]\n"
          ]
        }
      ],
      "source": [
        "print(\"Generate sentences:\")\n",
        "N_SENTS=5\n",
        "\n",
        "print(\"Bigrams without smoothing\")\n",
        "bigram_lm_generations = [bigram_lm.generate() for i in range(N_SENTS)]\n",
        "print(bigram_lm_generations)\n",
        "\n",
        "print(\"Bigrams with smoothing\")\n",
        "bigram_lm_generations_smoothed = [bigram_lm_smooth.generate()\n",
        "                                          for i in range(N_SENTS)]\n",
        "print(bigram_lm_generations_smoothed)\n",
        "\n",
        "print(\"unigrams without smoothing\")\n",
        "unigram_lm_generations = [unigram_lm.generate() for i in range(N_SENTS)]\n",
        "print(unigram_lm_generations)\n",
        "\n",
        "print(\"unigrams with smoothing\")\n",
        "unigram_lm_generations_smoothed = [unigram_lm_smooth.generate()\n",
        "                                                    for i in range(N_SENTS)]\n",
        "print(unigram_lm_generations_smoothed)\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "I have observed the following things:\n",
        "\n",
        "### Bigram Model\n",
        "- **Without Smoothing**: The sentences are understandable but some are not proper and not sound natural.\n",
        "\n",
        "- **With Smoothing**: The sentences sound more natural and the flow is good.\n",
        "\n",
        "### Unigram Model\n",
        "- **Without Smoothing**: The sentences look like random words\n",
        "\n",
        "- **With Smoothing**: The sentences are still random, but smoothing adds more variety than before\n",
        "\n",
        "### To Conclude\n",
        "- **Bigram models** did a better job of creating sentences because they consider the word before the current one.\n",
        "- **Unigram models** produced random sentences because they don’t think about the order of words and do not have any context.\n",
        "- **Smoothing** helped both models by making the sentences less repetitive and allowing them to handle words they haven’t seen together before.\n",
        "\n",
        "In short, the bigram model with smoothing gives the best sentences than unigram."
      ],
      "metadata": {
        "id": "TmqLI0aMK6Dc"
      }
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "Rl-yy9YZveNC"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "5TaB6HFp7PzZ"
      },
      "execution_count": null,
      "outputs": []
    }
  ],
  "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.9.7"
    },
    "colab": {
      "provenance": [],
      "include_colab_link": true
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}