main.ipynb

{
 "metadata": {
  "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.7-final"
  },
  "orig_nbformat": 2,
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2,
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "import random\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import nltk\n",
    "\n",
    "from libraries import utils_preprocess as upp, utils_ngram as ung, utils_perplexity as up, utils_suggestions as suggest"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Load Indonesian Corpus"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "Data type: <class 'str'>\nNumber of letters: 777735639\n-------\nFirst 300 letters of the data\n-------\n"
    },
    {
     "output_type": "display_data",
     "data": {
      "text/plain": "'berkas dna structure key labelled pn nobb png jmpl ka px struktur heliks ganda dna atom atom pada struktur tersebut diwarnai sesuai dengan unsur kimianya dan struktur detail dua pasangan basa ditunjukkan oleh gambar kanan bawah gambaran tiga dimensi dna asam lebih dikenal dengan singkatan dna bahasa'"
     },
     "metadata": {}
    },
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "-------\nLast 300 letters of the data\n-------\n"
    },
    {
     "output_type": "display_data",
     "data": {
      "text/plain": "'k bola spanyol yang berbasis di kota getxo dekat bilbao di komunitas otonom negara basque didirikan pada tahun saat ini bermain di segunda división group mengadakan pertandingan kandang di campo municipal de gobela dengan kapasitas kursi referensi pranala luar official website futbolme team profile\\n'"
     },
     "metadata": {}
    }
   ],
   "source": [
    "data = upp.get_CorpusData(verbose=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Split into train and test sets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "tokenized_data = upp.get_tokenized_data(data)\n",
    "random.seed(87)\n",
    "random.shuffle(tokenized_data)\n",
    "\n",
    "train_size = int(len(tokenized_data) * 0.8)\n",
    "train_data = tokenized_data[0:train_size]\n",
    "test_data = tokenized_data[train_size:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "403950 data are split into 323160 train and 80790 test set\n\nFirst training sample: ['cleomenes', 'laetabilis', 'adalah', 'spesies', 'kumbang', 'tanduk', 'panjang', 'yang', 'tergolong', 'famili', 'cerambycidae', 'spesies', 'ini', 'juga', 'merupakan', 'bagian', 'dari', 'genus', 'cleomenes', 'ordo', 'coleoptera', 'kelas', 'insecta', 'filum', 'arthropoda', 'dan', 'kingdom', 'animalia', 'larva', 'kumbang', 'ini', 'biasanya', 'mengebor', 'ke', 'dalam', 'kayu', 'dan', 'dapat', 'menyebabkan', 'kerusakan', 'pada', 'batang', 'kayu', 'hidup', 'atau', 'kayu', 'yang', 'telah', 'ditebang', 'referensi', 'titan', 'cerambycidae', 'database', 'tavakilian', 'mei', 'kategori', 'cerambycidae']\n\nFirst test sample : ['katie', 'stevens', 'katie', 'stevens', 'adalah', 'seorang', 'aktris', 'dan', 'penyanyi', 'amerika', 'ia', 'merupakan', 'bungsu', 'dari', 'kedua', 'orang', 'bersaudara', 'ia', 'juga', 'adalah', 'seorang', 'anak', 'keturunan', 'portugis', 'ia', 'mampu', 'berbahasa', 'inggris', 'spanyol', 'dan', 'portugis', 'secara', 'fasih', 'namanya', 'dikenal', 'luas', 'setelah', 'ia', 'berhasil', 'menjadi', 'salah', 'satu', 'finalis', 'dalam', 'american', 'idol', 'musim', 'kesembilan', 'sebelum', 'mengikuti', 'american', 'idol', 'ia', 'pernah', 'memenangkan', 'kompetisi', 'westbury', 'outstanding', 'teen', 'dan', 'runner', 'up', 'miss', 'teen', 'connecticut', 'ia', 'tersisih', 'dari', 'american', 'idol', 'pada', 'posisi', 'delapan', 'besar', 'ia', 'berhak', 'untuk', 'mengikuti', 'tour', 'idol', 'pada', 'musim', 'panas', 'setelah', 'tersisih', 'ia', 'berniat', 'untuk', 'terus', 'mengembangkan', 'bakatnya', 'di', 'bidang', 'menyanyi', 'referensi', 'kategori', 'penyanyi', 'kategori', 'american', 'idol']\n\n"
    }
   ],
   "source": [
    "print(\"{} data are split into {} train and {} test set\".format(len(tokenized_data), len(train_data), len(test_data)), end='\\n\\n')\n",
    "print(f\"First training sample: {train_data[0]}\", end='\\n\\n')\n",
    "print(f\"First test sample : {test_data[0]}\", end='\\n\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Preprocess the train and test data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "First preprocessed training sample : ['cleomenes', 'laetabilis', 'adalah', 'spesies', 'kumbang', 'tanduk', 'panjang', 'yang', 'tergolong', 'famili', 'cerambycidae', 'spesies', 'ini', 'juga', 'merupakan', 'bagian', 'dari', 'genus', 'cleomenes', 'ordo', 'coleoptera', 'kelas', 'insecta', 'filum', 'arthropoda', 'dan', 'kingdom', 'animalia', 'larva', 'kumbang', 'ini', 'biasanya', 'mengebor', 'ke', 'dalam', 'kayu', 'dan', 'dapat', 'menyebabkan', 'kerusakan', 'pada', 'batang', 'kayu', 'hidup', 'atau', 'kayu', 'yang', 'telah', 'ditebang', 'referensi', 'titan', 'cerambycidae', 'database', 'tavakilian', 'mei', 'kategori', 'cerambycidae']\n\nFirst preprocessed test sample : ['katie', 'stevens', 'katie', 'stevens', 'adalah', 'seorang', 'aktris', 'dan', 'penyanyi', 'amerika', 'ia', 'merupakan', 'bungsu', 'dari', 'kedua', 'orang', 'bersaudara', 'ia', 'juga', 'adalah', 'seorang', 'anak', 'keturunan', 'portugis', 'ia', 'mampu', 'berbahasa', 'inggris', 'spanyol', 'dan', 'portugis', 'secara', 'fasih', 'namanya', 'dikenal', 'luas', 'setelah', 'ia', 'berhasil', 'menjadi', 'salah', 'satu', 'finalis', 'dalam', 'american', 'idol', 'musim', 'kesembilan', 'sebelum', 'mengikuti', 'american', 'idol', 'ia', 'pernah', 'memenangkan', 'kompetisi', 'westbury', 'outstanding', 'teen', 'dan', 'runner', 'up', 'miss', 'teen', 'connecticut', 'ia', 'tersisih', 'dari', 'american', 'idol', 'pada', 'posisi', 'delapan', 'besar', 'ia', 'berhak', 'untuk', 'mengikuti', 'tour', 'idol', 'pada', 'musim', 'panas', 'setelah', 'tersisih', 'ia', 'berniat', 'untuk', 'terus', 'mengembangkan', 'bakatnya', 'di', 'bidang', 'menyanyi', 'referensi', 'kategori', 'penyanyi', 'kategori', 'american', 'idol']\n\nFirst 10 vocabulary : ['cleomenes', 'laetabilis', 'adalah', 'spesies', 'kumbang', 'tanduk', 'panjang', 'yang', 'tergolong', 'famili']\n\nSize of vocabulary: 700532\n"
    }
   ],
   "source": [
    "train_data, test_data, vocab = upp.preprocess_data(train_data, test_data, count_threshold=2)\n",
    "print(f\"First preprocessed training sample : {train_data[0]}\", end='\\n\\n')\n",
    "print(f\"First preprocessed test sample : {test_data[0]}\", end='\\n\\n')\n",
    "print(f\"First 10 vocabulary : {vocab[0:10]}\", end='\\n\\n')\n",
    "print(\"Size of vocabulary:\", len(vocab))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Test Auto-Complete System model using n-grams of varying length (unigrams, bigrams, trigrams, 4-grams...6-grams)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "Computing n-gram counts with n = 1 ...\nComputing n-gram counts with n = 2 ...\nComputing n-gram counts with n = 3 ...\nComputing n-gram counts with n = 4 ...\nComputing n-gram counts with n = 5 ...\n"
    }
   ],
   "source": [
    "n_gram_counts_list = []\n",
    "for n in range(1, 6):\n",
    "    print(\"Computing n-gram counts with n =\", n, \"...\")\n",
    "    n_model_counts = ung.count_n_grams(train_data, n)\n",
    "    n_gram_counts_list.append(n_model_counts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "The previous words are ['saya', 'akan', 'pergi'], the suggestions are:\n"
    },
    {
     "output_type": "display_data",
     "data": {
      "text/plain": "[('ke', 0.00877150045521738),\n ('ke', 0.00022113383162156725),\n ('tetapi', 4.282398485743896e-06),\n ('cleomenes', 1.4274824633779373e-06)]"
     },
     "metadata": {}
    }
   ],
   "source": [
    "previous_tokens = [\"saya\", \"akan\", \"pergi\"]\n",
    "suggest_words = suggest.get_suggestions(previous_tokens, n_gram_counts_list, vocab, k=1.0)\n",
    "\n",
    "print(f\"The previous words are {previous_tokens}, the suggestions are:\")\n",
    "display(suggest_words)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "The previous words are ['dia', 'pergi', 'untuk', 'membeli'], the suggestions are:\n"
    },
    {
     "output_type": "display_data",
     "data": {
      "text/plain": "[('saham', 0.00038925156125262566),\n ('barang', 6.697780469557163e-05),\n ('air', 1.4274498608236385e-05),\n ('jas', 2.854960851349326e-06)]"
     },
     "metadata": {}
    }
   ],
   "source": [
    "previous_tokens = [\"dia\", \"pergi\", \"untuk\", \"membeli\"]\n",
    "suggest_words = suggest.get_suggestions(previous_tokens, n_gram_counts_list, vocab, k=1.0)\n",
    "\n",
    "print(f\"The previous words are {previous_tokens}, the suggestions are:\")\n",
    "display(suggest_words)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "The previous words are ['hai', 'bagaimana', 'kabar'], the suggestions are:\n"
    },
    {
     "output_type": "display_data",
     "data": {
      "text/plain": "[('ini', 0.0006703093865892965),\n ('baik', 2.854956775954412e-06),\n ('cleomenes', 1.4274824633779373e-06),\n ('cleomenes', 1.4274824633779373e-06)]"
     },
     "metadata": {}
    }
   ],
   "source": [
    "previous_tokens = [\"hai\", \"bagaimana\", \"kabar\"]\n",
    "suggest_words = suggest.get_suggestions(previous_tokens, n_gram_counts_list, vocab, k=1.0)\n",
    "\n",
    "print(f\"The previous words are {previous_tokens}, the suggestions are:\")\n",
    "display(suggest_words)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "The previous words are ['bagaimana', 'cara', 'untuk', 'menemukan'], the suggestions are:\n"
    },
    {
     "output_type": "display_data",
     "data": {
      "text/plain": "[('makanan', 0.005202140309155767),\n ('dan', 9.827715867915499e-05),\n ('dan', 2.8549160226451938e-06),\n ('cleomenes', 1.4274824633779373e-06)]"
     },
     "metadata": {}
    }
   ],
   "source": [
    "previous_tokens = [\"bagaimana\", \"cara\", \"untuk\", \"menemukan\"]\n",
    "suggest_words = suggest.get_suggestions(previous_tokens, n_gram_counts_list, vocab, k=1.0)\n",
    "\n",
    "print(f\"The previous words are {previous_tokens}, the suggestions are:\")\n",
    "display(suggest_words)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "The previous words are ['bagaimana', 'cara', 'untuk', 'menemukan'], the suggestions are:\n"
    },
    {
     "output_type": "display_data",
     "data": {
      "text/plain": "[('sebuah', 0.0007987264827141698),\n ('solusi', 4.272919942571956e-05),\n ('semua', 2.8549160226451938e-06),\n ('spesies', 1.4274824633779373e-06)]"
     },
     "metadata": {}
    }
   ],
   "source": [
    "previous_tokens = [\"bagaimana\", \"cara\", \"untuk\", \"menemukan\"]\n",
    "suggest_words = suggest.get_suggestions(previous_tokens, n_gram_counts_list, vocab, k=1.0, start_with=\"s\")\n",
    "\n",
    "print(f\"The previous words are {previous_tokens}, the suggestions are:\")\n",
    "display(suggest_words)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "---\n",
    "# FORMULAS EXPLANATION BEHIND THE LANGUAGE MODEL\n",
    "\n",
    "A key building block for an auto-complete system is a language model. A language model assigns the probability to a sequence of words, in a way that more \"likely\" sequences receive higher scores.\n",
    "We can take advantage of this probability calculation to develop an auto-complete system.  \n",
    "Suppose the user typed \n",
    ">\"I eat scrambled\"\n",
    "Then we can find a word `x`  such that \"I eat scrambled x\" receives the highest probability.  If x = \"eggs\", the sentence would be\n",
    ">\"I eat scrambled eggs\"\n",
    "\n",
    "While a variety of language models have been developed, this assignment uses **N-grams**, a simple but powerful method for language modeling.\n",
    "- N-grams are also used in machine translation and speech recognition. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Preprocess Data\n",
    "\n",
    "### 1.1 Split data into sentences using \"\\n\" as the delimiter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "\nBalonku ada 5.\nRupa-rupa warnanya.\nMerah kuning kelabu.\n\n\n"
    },
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "['Balonku ada 5.', 'Rupa-rupa warnanya.', 'Merah kuning kelabu.']"
     },
     "metadata": {},
     "execution_count": 12
    }
   ],
   "source": [
    "# test code\n",
    "x = \"\"\"\n",
    "Balonku ada 5.\\nRupa-rupa warnanya.\\nMerah kuning kelabu.\\n\n",
    "\"\"\"\n",
    "print(x)\n",
    "upp.split_to_sentences(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.2 Split each sentence into tokens\n",
    "\n",
    "The next step is to tokenize sentences (split a sentence into a list of words). \n",
    "- Convert all tokens into lower case so that words which are capitalized (for example, at the start of a sentence) in the original text are treated the same as the lowercase versions of the words.\n",
    "- Append each tokenized list of words into a list of tokenized sentences."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "[['balonku', 'ada', '5', '.'],\n ['rupa-rupa', 'warnanya', '.'],\n ['merah', 'kuning', 'kelabu', '.']]"
     },
     "metadata": {},
     "execution_count": 13
    }
   ],
   "source": [
    "# test code\n",
    "sentences = [\"Balonku ada 5.\", \"Rupa-rupa warnanya.\", \"Merah kuning kelabu.\"]\n",
    "upp.tokenize_sentences(sentences)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "[['balonku', 'ada', '5', '.'],\n ['rupa-rupa', 'warnanya', '.'],\n ['merah', 'kuning', 'kelabu', '.']]"
     },
     "metadata": {},
     "execution_count": 14
    }
   ],
   "source": [
    "# test code\n",
    "x = \"Balonku ada 5.\\nRupa-rupa warnanya.\\nMerah kuning kelabu.\"\n",
    "upp.get_tokenized_data(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.3 Find tokens that appear at least N times in the training data\n",
    "\n",
    "We won't use all the tokens (words) appearing in the data for training.  Instead, we will use the more frequently used words.  \n",
    "- We will focus on the words that appear at least N times in the data.\n",
    "- First count how many times each word appears in the data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "{'ayah': 1,\n 'memetik': 1,\n 'mangga': 1,\n '.': 3,\n 'mobil': 1,\n 'berwarna': 1,\n 'kuning': 1,\n 'bunga': 1,\n 'ditepi': 1,\n 'jalan': 1}"
     },
     "metadata": {},
     "execution_count": 15
    }
   ],
   "source": [
    "# test code\n",
    "tokenized_sentences = [['ayah', 'memetik', 'mangga', '.'], ['mobil', 'berwarna', 'kuning', '.'], ['bunga', 'ditepi', 'jalan', '.']]\n",
    "upp.count_words(tokenized_sentences)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.4 Handling 'Out of Vocabulary' words\n",
    "\n",
    "If our model is performing autocomplete, but encounters a word that it never saw during training, it won't have an input word to help it determine the next word to suggest. The model will not be able to predict the next word because there are no counts for the current word. \n",
    "- This 'new' word is called an 'unknown word', or <b>out of vocabulary (OOV)</b> words.\n",
    "- The percentage of unknown words in the test set is called the <b> OOV </b> rate. \n",
    "\n",
    "To handle unknown words during prediction, use a special token to represent all unknown words 'unk'. \n",
    "- Modify the training data so that it has some 'unknown' words to train on.\n",
    "- Words to convert into \"unknown\" words are those that do not occur very frequently in the training set.\n",
    "- Create a list of the most frequent words in the training set, called the <b> closed vocabulary </b>. \n",
    "- Convert all the other words that are not part of the closed vocabulary to the token 'unk'. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "Closed vocabulary : ['.']\n"
    }
   ],
   "source": [
    "# test code\n",
    "tokenized_sentences = [['ayah', 'memetik', 'mangga', '.'], ['mobil', 'berwarna', 'kuning', '.'], ['bunga', 'ditepi', 'jalan', '.']]\n",
    "tmp_closed_vocab = upp.get_words_with_nplus_frequency(tokenized_sentences, count_threshold=2)\n",
    "print(f\"Closed vocabulary : {tmp_closed_vocab}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The words that appear `count_threshold` times or more are in the closed vocabulary. \n",
    "- All other words are regarded as `unknown`.\n",
    "- Replace words not in the closed vocabulary with the token `<unk>`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "Original sentence: [['anjing', 'lari'], ['kucing', 'tidur']]\ntokenized_sentences with less frequent words converted to '<unk>': [['anjing', '<unk>'], ['<unk>', 'tidur']]\n"
    }
   ],
   "source": [
    "# test code\n",
    "tokenized_sentences = [[\"anjing\", \"lari\"], [\"kucing\", \"tidur\"]]\n",
    "vocabulary = [\"anjing\", \"tidur\"]\n",
    "tmp_replaced_tokenized_sentences = upp.replace_oov_words_by_unk(tokenized_sentences, vocabulary)\n",
    "print(f\"Original sentence: {tokenized_sentences}\")\n",
    "print(f\"tokenized_sentences with less frequent words converted to '<unk>': {tmp_replaced_tokenized_sentences}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "tmp_train_repl : [['ayah', 'memetik', 'mangga', '.'], ['mobil', 'ayah', 'rusak', '.']]\n\ntmp_test_repl : [['mangga', '<unk>', '<unk>', '.']]\n\ntmp_vocab : ['ayah', 'memetik', 'mangga', '.', 'mobil', 'rusak']\n"
    }
   ],
   "source": [
    "# test code\n",
    "tmp_train = [['ayah', 'memetik', 'mangga', '.'], ['mobil', 'ayah', 'rusak', '.']]\n",
    "tmp_test = [['mangga', 'ditepi', 'jalan', '.']]\n",
    "\n",
    "tmp_train_repl, tmp_test_repl, tmp_vocab = upp.preprocess_data(tmp_train, tmp_test, count_threshold = 1)\n",
    "\n",
    "print(f\"tmp_train_repl : {tmp_train_repl}\", end='\\n\\n')\n",
    "print(f\"tmp_test_repl : {tmp_test_repl}\", end='\\n\\n')\n",
    "print(f\"tmp_vocab : {tmp_vocab}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "Uni-gram: {('<s>',): 2, ('saya',): 1, ('menyukai',): 2, ('kucing',): 2, ('hitam',): 2, ('<e>',): 2, ('anjing',): 1, ('ini',): 1, ('itu',): 1}\nBi-gram: {('<s>', '<s>'): 2, ('<s>', 'saya'): 1, ('saya', 'menyukai'): 1, ('menyukai', 'kucing'): 2, ('kucing', 'hitam'): 2, ('hitam', '<e>'): 1, ('<s>', 'anjing'): 1, ('anjing', 'ini'): 1, ('ini', 'menyukai'): 1, ('hitam', 'itu'): 1, ('itu', '<e>'): 1}\n"
    }
   ],
   "source": [
    "# test code\n",
    "sentences = [['saya', 'menyukai', 'kucing', 'hitam'], ['anjing', 'ini', 'menyukai', 'kucing', 'hitam', 'itu']]\n",
    "print(\"Uni-gram: {}\".format(ung.count_n_grams(sentences, 1)))\n",
    "print(\"Bi-gram: {}\".format(ung.count_n_grams(sentences, 2)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## 2. Develop n-gram based language models\n",
    "\n",
    "- Assume the probability of the next word depends only on the previous n-gram.\n",
    "- The previous n-gram is the series of the previous 'n' words.\n",
    "\n",
    "The conditional probability for the word at position 't' in the sentence, given that the words preceding it are $w_{t-1}, w_{t-2} \\cdots w_{t-n}$ is:\n",
    "\n",
    "$$ P(w_t | w_{t-1}\\dots w_{t-n}) \\tag{1}$$\n",
    "\n",
    "We can estimate this probability  by counting the occurrences of these series of words in the training data.\n",
    "- The probability can be estimated as a ratio, where\n",
    "- The numerator is the number of times word 't' appears after words t-1 through t-n appear in the training data.\n",
    "- The denominator is the number of times word t-1 through t-n appears in the training data.\n",
    "\n",
    "$$ \\hat{P}(w_t | w_{t-1}\\dots w_{t-n}) = \\frac{C(w_{t-1}\\dots w_{t-n}, w_n)}{C(w_{t-1}\\dots w_{t-n})} \\tag{2} $$\n",
    "\n",
    "- The function $C(\\cdots)$ denotes the number of occurence of the given sequence. \n",
    "- $\\hat{P}$ means the estimation of $P$. \n",
    "- Notice that denominator of the equation (2) is the number of occurence of the previous $n$ words, and the numerator is the same sequence followed by the word $w_t$.\n",
    "\n",
    "The equation (2) tells us that to estimate probabilities based on n-grams, we need the counts of n-grams (for denominator) and (n+1)-grams (for numerator)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.1 Computes the counts of n-grams \n",
    "\n",
    "When computing the counts for n-grams, prepare the sentence beforehand by prepending $n-1$ starting markers \"<s\\>\" to indicate the beginning of the sentence.  \n",
    "- For example, in the bi-gram model (N=2), a sequence with two start tokens \"<s\\><s\\>\" should predict the first word of a sentence.\n",
    "- So, if the sentence is \"I like food\", modify it to be \"<s\\><s\\> I like food\".\n",
    "- Also prepare the sentence for counting by appending an end token \"<e\\>\" so that the model can predict when to finish a sentence.\n",
    "- The key of each key-value pair in the dictionary is a **tuple** of n words (and not a list)\n",
    "- The value in the key-value pair is the number of occurrences.  \n",
    "- The reason for using a tuple as a key instead of a list is because a list in Python is a mutable object (it can be changed after it is first created).  A tuple is \"immutable\", so it cannot be altered after it is first created.  This makes a tuple suitable as a data type for the key in a dictionary."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "Uni-gram: {('<s>',): 2, ('saya',): 1, ('menyukai',): 2, ('kucing',): 2, ('hitam',): 2, ('<e>',): 2, ('anjing',): 1, ('ini',): 1, ('itu',): 1}\n\nBi-gram: {('<s>', '<s>'): 2, ('<s>', 'saya'): 1, ('saya', 'menyukai'): 1, ('menyukai', 'kucing'): 2, ('kucing', 'hitam'): 2, ('hitam', '<e>'): 1, ('<s>', 'anjing'): 1, ('anjing', 'ini'): 1, ('ini', 'menyukai'): 1, ('hitam', 'itu'): 1, ('itu', '<e>'): 1}\n"
    }
   ],
   "source": [
    "# test code\n",
    "sentences = [['saya', 'menyukai', 'kucing', 'hitam'], ['anjing', 'ini', 'menyukai', 'kucing', 'hitam', 'itu']]\n",
    "print(\"Uni-gram: {}\".format(ung.count_n_grams(sentences, 1)), end='\\n\\n')\n",
    "print(\"Bi-gram: {}\".format(ung.count_n_grams(sentences, 2)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.2 Estimate the probability of a word given and for all words\n",
    "\n",
    "$$ \\hat{P}(w_t | w_{t-1}\\dots w_{t-n}) = \\frac{C(w_{t-1}\\dots w_{t-n}, w_n)}{C(w_{t-1}\\dots w_{t-n})} \\tag{2} $$\n",
    "\n",
    "This formula doesn't work when a count of an n-gram is zero..\n",
    "- Suppose we encounter an n-gram that did not occur in the training data.  \n",
    "- Then, the equation (2) cannot be evaluated (it becomes zero divided by zero).\n",
    "\n",
    "A way to handle zero counts is to add k-smoothing.  \n",
    "- K-smoothing adds a positive constant $k$ to each numerator and $k \\times |V|$ in the denominator, where $|V|$ is the number of words in the vocabulary.\n",
    "\n",
    "$$ \\hat{P}(w_t | w_{t-1}\\dots w_{t-n}) = \\frac{C(w_{t-1}\\dots w_{t-n}, w_n) + k}{C(w_{t-1}\\dots w_{t-n}) + k|V|} \\tag{3} $$\n",
    "\n",
    "\n",
    "For n-grams that have a zero count, the equation (3) becomes $\\frac{1}{|V|}$.\n",
    "- This means that any n-gram with zero count has the same probability of $\\frac{1}{|V|}$.\n",
    "\n",
    "Define a function that computes the probability estimate (3) from n-gram counts and a constant $k$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "The estimated probability of word 'cat' given the previous n-gram 'a' is: 0.1429\n"
    }
   ],
   "source": [
    "# test code\n",
    "sentences = [['saya', 'menyukai', 'kucing', 'hitam'], ['anjing', 'ini', 'menyukai', 'kucing', 'hitam', 'itu']]\n",
    "unique_words = list(set(sentences[0] + sentences[1]))\n",
    "\n",
    "unigram_counts = ung.count_n_grams(sentences, 1)\n",
    "bigram_counts = ung.count_n_grams(sentences, 2)\n",
    "tmp_prob = ung.estimate_probability(\"cat\", \"a\", unigram_counts, bigram_counts, len(unique_words), k=1)\n",
    "\n",
    "print(f\"The estimated probability of word 'cat' given the previous n-gram 'a' is: {tmp_prob:.4f}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "{'saya': 0.1111111111111111,\n 'menyukai': 0.1111111111111111,\n 'ini': 0.1111111111111111,\n 'hitam': 0.1111111111111111,\n 'itu': 0.1111111111111111,\n 'kucing': 0.1111111111111111,\n 'anjing': 0.1111111111111111,\n '<e>': 0.1111111111111111,\n '<unk>': 0.1111111111111111}"
     },
     "metadata": {},
     "execution_count": 22
    }
   ],
   "source": [
    "# test code\n",
    "sentences = [['saya', 'menyukai', 'kucing', 'hitam'], ['anjing', 'ini', 'menyukai', 'kucing', 'hitam', 'itu']]\n",
    "unique_words = list(set(sentences[0] + sentences[1]))\n",
    "unigram_counts = ung.count_n_grams(sentences, 1)\n",
    "bigram_counts = ung.count_n_grams(sentences, 2)\n",
    "ung.estimate_probabilities(\"a\", unigram_counts, bigram_counts, unique_words, k=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.3 Count and probability matrices\n",
    "\n",
    "The n-gram counts computed above are sufficient for computing the probabilities of the next word which can be more intuitive to present them as count or probability matrices."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "\ntrigram counts\n"
    },
    {
     "output_type": "display_data",
     "data": {
      "text/plain": "                    saya  menyukai  ini  hitam  itu  kucing  anjing  <e>  \\\n(kucing, hitam)      0.0       0.0  0.0    0.0  1.0     0.0     0.0  1.0   \n(hitam,)             0.0       0.0  0.0    0.0  0.0     0.0     0.0  1.0   \n(<s>, <s>)           1.0       0.0  0.0    0.0  0.0     0.0     1.0  0.0   \n(ini, menyukai)      0.0       0.0  0.0    0.0  0.0     1.0     0.0  0.0   \n(<s>, anjing)        0.0       0.0  1.0    0.0  0.0     0.0     0.0  0.0   \n(<s>, saya)          0.0       1.0  0.0    0.0  0.0     0.0     0.0  0.0   \n(menyukai, kucing)   0.0       0.0  0.0    2.0  0.0     0.0     0.0  0.0   \n(hitam, itu)         0.0       0.0  0.0    0.0  0.0     0.0     0.0  1.0   \n(itu,)               0.0       0.0  0.0    0.0  0.0     0.0     0.0  1.0   \n(saya, menyukai)     0.0       0.0  0.0    0.0  0.0     1.0     0.0  0.0   \n(anjing, ini)        0.0       1.0  0.0    0.0  0.0     0.0     0.0  0.0   \n\n                    <unk>  \n(kucing, hitam)       0.0  \n(hitam,)              0.0  \n(<s>, <s>)            0.0  \n(ini, menyukai)       0.0  \n(<s>, anjing)         0.0  \n(<s>, saya)           0.0  \n(menyukai, kucing)    0.0  \n(hitam, itu)          0.0  \n(itu,)                0.0  \n(saya, menyukai)      0.0  \n(anjing, ini)         0.0  ",
      "text/html": "<div>\n<style scoped>\n    .dataframe tbody tr th:only-of-type {\n        vertical-align: middle;\n    }\n\n    .dataframe tbody tr th {\n        vertical-align: top;\n    }\n\n    .dataframe thead th {\n        text-align: right;\n    }\n</style>\n<table border=\"1\" class=\"dataframe\">\n  <thead>\n    <tr style=\"text-align: right;\">\n      <th></th>\n      <th>saya</th>\n      <th>menyukai</th>\n      <th>ini</th>\n      <th>hitam</th>\n      <th>itu</th>\n      <th>kucing</th>\n      <th>anjing</th>\n      <th>&lt;e&gt;</th>\n      <th>&lt;unk&gt;</th>\n    </tr>\n  </thead>\n  <tbody>\n    <tr>\n      <th>(kucing, hitam)</th>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>1.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>1.0</td>\n      <td>0.0</td>\n    </tr>\n    <tr>\n      <th>(hitam,)</th>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>1.0</td>\n      <td>0.0</td>\n    </tr>\n    <tr>\n      <th>(&lt;s&gt;, &lt;s&gt;)</th>\n      <td>1.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>1.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n    </tr>\n    <tr>\n      <th>(ini, menyukai)</th>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>1.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n    </tr>\n    <tr>\n      <th>(&lt;s&gt;, anjing)</th>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>1.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n    </tr>\n    <tr>\n      <th>(&lt;s&gt;, saya)</th>\n      <td>0.0</td>\n      <td>1.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n    </tr>\n    <tr>\n      <th>(menyukai, kucing)</th>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>2.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n    </tr>\n    <tr>\n      <th>(hitam, itu)</th>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>1.0</td>\n      <td>0.0</td>\n    </tr>\n    <tr>\n      <th>(itu,)</th>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>1.0</td>\n      <td>0.0</td>\n    </tr>\n    <tr>\n      <th>(saya, menyukai)</th>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>1.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n    </tr>\n    <tr>\n      <th>(anjing, ini)</th>\n      <td>0.0</td>\n      <td>1.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n      <td>0.0</td>\n    </tr>\n  </tbody>\n</table>\n</div>"
     },
     "metadata": {}
    }
   ],
   "source": [
    "# test code\n",
    "sentences = [['saya', 'menyukai', 'kucing', 'hitam'], ['anjing', 'ini', 'menyukai', 'kucing', 'hitam', 'itu']]\n",
    "unique_words = list(set(sentences[0] + sentences[1]))\n",
    "trigram_counts = ung.count_n_grams(sentences, 3)\n",
    "\n",
    "print('\\ntrigram counts')\n",
    "display(ung.make_count_matrix(trigram_counts, unique_words))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "trigram probabilities\n"
    },
    {
     "output_type": "display_data",
     "data": {
      "text/plain": "                        saya  menyukai       ini     hitam       itu  \\\n(kucing, hitam)     0.090909  0.090909  0.090909  0.090909  0.181818   \n(hitam,)            0.100000  0.100000  0.100000  0.100000  0.100000   \n(<s>, <s>)          0.181818  0.090909  0.090909  0.090909  0.090909   \n(ini, menyukai)     0.100000  0.100000  0.100000  0.100000  0.100000   \n(<s>, anjing)       0.100000  0.100000  0.200000  0.100000  0.100000   \n(<s>, saya)         0.100000  0.200000  0.100000  0.100000  0.100000   \n(menyukai, kucing)  0.090909  0.090909  0.090909  0.272727  0.090909   \n(hitam, itu)        0.100000  0.100000  0.100000  0.100000  0.100000   \n(itu,)              0.100000  0.100000  0.100000  0.100000  0.100000   \n(saya, menyukai)    0.100000  0.100000  0.100000  0.100000  0.100000   \n(anjing, ini)       0.100000  0.200000  0.100000  0.100000  0.100000   \n\n                      kucing    anjing       <e>     <unk>  \n(kucing, hitam)     0.090909  0.090909  0.181818  0.090909  \n(hitam,)            0.100000  0.100000  0.200000  0.100000  \n(<s>, <s>)          0.090909  0.181818  0.090909  0.090909  \n(ini, menyukai)     0.200000  0.100000  0.100000  0.100000  \n(<s>, anjing)       0.100000  0.100000  0.100000  0.100000  \n(<s>, saya)         0.100000  0.100000  0.100000  0.100000  \n(menyukai, kucing)  0.090909  0.090909  0.090909  0.090909  \n(hitam, itu)        0.100000  0.100000  0.200000  0.100000  \n(itu,)              0.100000  0.100000  0.200000  0.100000  \n(saya, menyukai)    0.200000  0.100000  0.100000  0.100000  \n(anjing, ini)       0.100000  0.100000  0.100000  0.100000  ",
      "text/html": "<div>\n<style scoped>\n    .dataframe tbody tr th:only-of-type {\n        vertical-align: middle;\n    }\n\n    .dataframe tbody tr th {\n        vertical-align: top;\n    }\n\n    .dataframe thead th {\n        text-align: right;\n    }\n</style>\n<table border=\"1\" class=\"dataframe\">\n  <thead>\n    <tr style=\"text-align: right;\">\n      <th></th>\n      <th>saya</th>\n      <th>menyukai</th>\n      <th>ini</th>\n      <th>hitam</th>\n      <th>itu</th>\n      <th>kucing</th>\n      <th>anjing</th>\n      <th>&lt;e&gt;</th>\n      <th>&lt;unk&gt;</th>\n    </tr>\n  </thead>\n  <tbody>\n    <tr>\n      <th>(kucing, hitam)</th>\n      <td>0.090909</td>\n      <td>0.090909</td>\n      <td>0.090909</td>\n      <td>0.090909</td>\n      <td>0.181818</td>\n      <td>0.090909</td>\n      <td>0.090909</td>\n      <td>0.181818</td>\n      <td>0.090909</td>\n    </tr>\n    <tr>\n      <th>(hitam,)</th>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.200000</td>\n      <td>0.100000</td>\n    </tr>\n    <tr>\n      <th>(&lt;s&gt;, &lt;s&gt;)</th>\n      <td>0.181818</td>\n      <td>0.090909</td>\n      <td>0.090909</td>\n      <td>0.090909</td>\n      <td>0.090909</td>\n      <td>0.090909</td>\n      <td>0.181818</td>\n      <td>0.090909</td>\n      <td>0.090909</td>\n    </tr>\n    <tr>\n      <th>(ini, menyukai)</th>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.200000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n    </tr>\n    <tr>\n      <th>(&lt;s&gt;, anjing)</th>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.200000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n    </tr>\n    <tr>\n      <th>(&lt;s&gt;, saya)</th>\n      <td>0.100000</td>\n      <td>0.200000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n    </tr>\n    <tr>\n      <th>(menyukai, kucing)</th>\n      <td>0.090909</td>\n      <td>0.090909</td>\n      <td>0.090909</td>\n      <td>0.272727</td>\n      <td>0.090909</td>\n      <td>0.090909</td>\n      <td>0.090909</td>\n      <td>0.090909</td>\n      <td>0.090909</td>\n    </tr>\n    <tr>\n      <th>(hitam, itu)</th>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.200000</td>\n      <td>0.100000</td>\n    </tr>\n    <tr>\n      <th>(itu,)</th>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.200000</td>\n      <td>0.100000</td>\n    </tr>\n    <tr>\n      <th>(saya, menyukai)</th>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.200000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n    </tr>\n    <tr>\n      <th>(anjing, ini)</th>\n      <td>0.100000</td>\n      <td>0.200000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n      <td>0.100000</td>\n    </tr>\n  </tbody>\n</table>\n</div>"
     },
     "metadata": {}
    }
   ],
   "source": [
    "# test code\n",
    "sentences = [['saya', 'menyukai', 'kucing', 'hitam'], ['anjing', 'ini', 'menyukai', 'kucing', 'hitam', 'itu']]\n",
    "unique_words = list(set(sentences[0] + sentences[1]))\n",
    "trigram_counts = ung.count_n_grams(sentences, 3)\n",
    "\n",
    "print(\"trigram probabilities\")\n",
    "display(ung.make_probability_matrix(trigram_counts, unique_words, k=1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## 3. Perplexity\n",
    "\n",
    "Wou will generate the perplexity score to evaluate your model on the test set. \n",
    "- we will also use back-off when needed. \n",
    "- Perplexity is used as an evaluation metric of our language model. \n",
    "- To calculate the  the perplexity score of the test set on an n-gram model, use: \n",
    "\n",
    "$$ PP(W) =\\sqrt[N]{ \\prod_{t=n+1}^N \\frac{1}{P(w_t | w_{t-n} \\cdots w_{t-1})} } \\tag{4}$$\n",
    "\n",
    "- where $N$ is the length of the sentence.\n",
    "- $n$ is the number of words in the n-gram (e.g. 2 for a bigram).\n",
    "- In math, the numbering starts at one and not zero.\n",
    "\n",
    "In code, array indexing starts at zero, so the code will use ranges for $t$ according to this formula:\n",
    "\n",
    "$$ PP(W) =\\sqrt[N]{ \\prod_{t=n}^{N-1} \\frac{1}{P(w_t | w_{t-n} \\cdots w_{t-1})} } \\tag{4.1}$$\n",
    "\n",
    "The higher the probabilities are, the lower the perplexity will be. \n",
    "- The more the n-grams tell us about the sentence, the lower the perplexity score will be. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "Perplexity for first train sample: 3.0000\nPerplexity for test sample: 4.2426\n"
    }
   ],
   "source": [
    "# test your code\n",
    "sentences = [['saya', 'menyukai', 'kucing', 'hitam'], ['anjing', 'ini', 'menyukai', 'kucing', 'hitam', 'itu']]\n",
    "unique_words = list(set(sentences[0] + sentences[1]))\n",
    "\n",
    "unigram_counts = ung.count_n_grams(sentences, 1)\n",
    "bigram_counts = ung.count_n_grams(sentences, 2)\n",
    "\n",
    "\n",
    "perplexity_train1 = up.calculate_perplexity(sentences[0], unigram_counts, bigram_counts, len(unique_words), k=1.0)\n",
    "print(f\"Perplexity for first train sample: {perplexity_train1:.4f}\")\n",
    "\n",
    "test_sentence = ['saya', 'menyukai', 'anjing', 'hitam']\n",
    "perplexity_test = up.calculate_perplexity(test_sentence, unigram_counts, bigram_counts, len(unique_words), k=1.0)\n",
    "print(f\"Perplexity for test sample: {perplexity_test:.4f}\")"
   ]
  }
 ]
}