homeworks/homework2/Homework2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Introduction\n",
    "This homework consists of two parts: in the first part, you will solve problems using the material from the lectures; in the second part you will get started with [PyTorch](https://pytorch.org/docs/stable/index.html). \n",
    "\n",
    "The first section consists of three problems:\n",
    "1. [Huffman algorithm](https://en.wikipedia.org/wiki/Huffman_coding) for encoding symbols  \n",
    "    __Note__: For this problem, you are not required to submit any code; however, you might find it faster/more convenient to implement the algorithm yourself.\n",
    "2. [Documents representation](https://en.wikipedia.org/wiki/Bag-of-words_model) and similarity metrics  \n",
    "    __Note__: For this problem, the starter code is written for you. Complete the missing parts to answer the questions.\n",
    "3. Formulation of NLP tasks in terms of Machine Learning  \n",
    "    __Note__: You don't need to submit any code for this problem.\n",
    "\n",
    "In the second section, you will be asked to complete the missing code that aims to parse and format the input data. Upon completion of the assignment, you will have a dataset that is ready to be loaded in a [model](https://en.wikipedia.org/wiki/Word2vec) that you will be training in the next homework. Feel free to use your code in further homeworks and in your project.\n",
    "\n",
    "__You will need__ to have the following libraries installed (please make sure you followed the installation instructions in the class repository to install them):\n",
    "- [NLTK](http://www.nltk.org/)\n",
    "- [NumPy](http://www.numpy.org/)\n",
    "- [PyTorch](https://pytorch.org/)\n",
    "\n",
    "\n",
    "__You will learn:__\n",
    "- How to represent documents in a numeric form\n",
    "- How to use different similarity metrics used in NLP\n",
    "- How to formulate a given problem as a machine learning problem\n",
    "- Basics of PyTorch data loading and processing\n",
    "  - How to convert input data to numeric representation\n",
    "  - How to use built-in `Dataset` and `DataLoader` classes\n",
    "\n",
    "Once you complete this assignment, submit it as:\n",
    "\n",
    "`submit arum hw2 <name_of_your_notebook> <additional_files>`\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Make sure that execution of this cell doesn't return any errors. If it does, go the class repository and follow the environment setup instructions\n",
    "import string\n",
    "from queue import PriorityQueue\n",
    "from collections import defaultdict, Counter\n",
    "\n",
    "import numpy as np\n",
    "import torch\n",
    "from torch.utils.data import Dataset, DataLoader\n",
    "from nltk import word_tokenize"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Theoretical problems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 1. Huffman code\n",
    "_Headi_ is an artificially created language that uses the only the first 10 letters\n",
    "English alphabet. The following is a table of relative frequencies of symbols in\n",
    "Headi text:\n",
    "\n",
    "|Letter|Frequency|Letter|Frequency|\n",
    "|---|---|---|---|\n",
    "|a|8.1%|g|0.7%|\n",
    "|b|1.4%|h|4.0%|\n",
    "|c|2.7%|i|7.4%|\n",
    "|d|4.2%|j|9.0%|\n",
    "|e|12.7%|space|43.8%|\n",
    "|f|6.0%|\n",
    "\n",
    "__Instructions__:\n",
    "\n",
    "For this problem, please do the following:\n",
    "\n",
    " 1. Paste your answers to the following questions into the notebook; if you write any code for this problem, please also include it.\n",
    " 2. Submit the diagram of the resulting tree; please submit this electronically; it could just be a scan or a photo of a hand-drawn diagram, submitted as a separate file."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1.1 Build a Huffman code for this language. Show your work.\n",
    "__Note__: if you want to implement Huffman algorithm, you might find `PriorityQueue` class of the `queue` library useful.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.2 Record the word \"Headi\" using the resulted code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__YOUR ANSWER HERE__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.3 What is the expected length of an encoded message consisting of 100 letters?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__YOUR ANSWER HERE__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###  1.4 What is the entropy of the probability distribution over Headi symbols?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__YOUR ANSWER HERE__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###  1.5 Jensen-Shannon divergence\n",
    "\n",
    "[Jensen-Shannon divergence](https://en.wikipedia.org/wiki/Jensen%E2%80%93Shannon_divergence) is a measure of similarity between two probability distributions. It is widely used in machine learning in general and NLP in particular.\n",
    "\n",
    "_Idaeh_ and _Iliat_ are two other languages that use only the first 10 letters of the\n",
    "English alphabet. Below are the tables of relative frequencies of symbols in\n",
    "Idaeh and Iliat texts:\n",
    "\n",
    "_Idaeh_\n",
    "\n",
    "|Letter|Frequency|Letter|Frequency|\n",
    "|---|---|---|---|\n",
    "|a|7.1%|g|0.7%|\n",
    "|b|2.4%|h|3.0%|\n",
    "|c|2.7%|i|8.4%|\n",
    "|d|3.2%|j|9.0%|\n",
    "|e|14.7%|space|42.8%|\n",
    "|f|6.0%|\n",
    "\n",
    "_Iliat_\n",
    "\n",
    "|Letter|Frequency|Letter|Frequency|\n",
    "|---|---|---|---|\n",
    "|a|1.1%|g|0.7%|\n",
    "|b|8.4%|h|10.0%|\n",
    "|c|2.7%|i|1.4%|\n",
    "|d|4.2%|j|29.0%|\n",
    "|e|12.7%|space|23.8%|\n",
    "|f|6.0%|\n",
    "\n",
    "\n",
    "__Question__:\n",
    "Calculate the Jensen-Shannon divergence between each of these two languages and the _Headi_ language. Which language, Idaeh or Iliat, is closer to Headi in terms of Jensen-Shannon divergence (in other words, the divergence is lower)?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__YOUR ANSWER HERE__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 2. Computing similarity\n",
    "In this problem you will learn about the simplest way to represent a single document and will practice finding similarities between two documents. Follow the instructions below to complete the missing code and answer the questions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consider two documents $D_1$ and $D_2$:\n",
    "\n",
    "$D_1$:\n",
    "\n",
    "```\n",
    "dance little baby, dance up high,\n",
    "never mind baby, mother is nigh;\n",
    "crow and caper, caper and crow,\n",
    "there little baby, there you go;\n",
    "```\n",
    "\n",
    "$D_2$:\n",
    "\n",
    "```\n",
    "up to the ceiling, down to the ground\n",
    "backwards and forwards, round and round.\n",
    "dance little baby, mother will sing,\n",
    "with the merry coral, ding, ding, ding.\n",
    "```\n",
    "\n",
    "Consider a vector representation for each document that tracks _how many times each token occured in that document_. You can assume that the punctuation tokens are discarded.\n",
    "\n",
    "For example, the following document\n",
    "\n",
    "```\n",
    "Jingle bells, jingle bells, jingle all the way\n",
    "```\n",
    "\n",
    "would be represented by the vector:\n",
    "\n",
    "$\\langle jingle: 3, bells: 2, all: 1, the: 1, way: 1 \\rangle$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.1 Compute the following similarity measures for these two documents:\n",
    "\n",
    "#### - Cosine similarity\n",
    "#### - Euclidean distance\n",
    "\n",
    "------\n",
    "In order to compute the measures you will need to do the following:\n",
    "1. Tokenize both documents ignoring punctuation\n",
    "2. Build the representation of each of the documents based on the counts of the words it contains\n",
    "3. Calculate the similarity measures using the following equations:\n",
    "\n",
    "    $\\text{Cosine similarity} = \\frac{\\mathbf{D_1}\\mathbf{D_2}}{||\\mathbf{D_1}|| ||\\mathbf{D_2}||}$\n",
    "\n",
    "    $\\text{Euclidean distance} = \\sqrt{\\sum_i{(D_{1_i} - D_{2_i})^2}}$\n",
    "\n",
    "\n",
    "#### Instructions:\n",
    "1. Complete the code in the `tokenize_doc` function that takes the input text and returns a list of tokens\n",
    "2. Complete the code in the `get_doc_vector` function that takes a list of tokens of a given document and a vocabulary consisting of tokens that will be counted in every document\n",
    "3. Complete the code in the `cosine_similarity` function that takes two vectors and returns a single float number reflecting the cosine similarity of the two vectors\n",
    "4. Complete the code in the `euclidean_distance` function that takes two vectors and returns a single float number reflecting the euclidean distance between the two vectors\n",
    "\n",
    "__Notes__:\n",
    "- In the previous homework you familiarized yourself with the `spaCy` library that efficiently processes input text. In the current problem, however, you are only required to do very basic tokenization of very short texts. For such purposes you can use the `nltk` library, which is another widespread tool for processing raw texts. Use `word_tokenize` function to obtain the tokens.\n",
    "- Make sure you ignore punctuation when you tokenize. You might find `string.punctuation` from the `string` package helpful.\n",
    "- Counting tokens should be easier if you use `Counter` class or `defaultdict` class from the `collections` package.\n",
    "- Note that one of the measures reflects how close two vectors are, while the other computes the distance between them. Despite different meanings, both are widely used in practice.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "doc1 = \"\"\"dance little baby, dance up high,\n",
    "never mind baby, mother is nigh;\n",
    "crow and caper, caper and crow,\n",
    "there little baby, there you go;\"\"\"\n",
    "\n",
    "doc2 = \"\"\"up to the ceiling, down to the ground\n",
    "backwards and forwards, round and round.\n",
    "dance little baby,mother will sing,\n",
    "with the merry coral, ding, ding, ding.\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def tokenize_doc(doc):\n",
    "    \"\"\"\n",
    "    Tokenize the document and return a list of tokens (lowercased) discarding all punctuation.\n",
    "    Args:\n",
    "        doc (str): The input document\n",
    "    Returns:\n",
    "        tokens (list): A list of tokens\n",
    "    \"\"\"\n",
    "\n",
    "    \n",
    "    ### YOUR CODE BELOW ###\n",
    "    tokens = []\n",
    "    ### YOUR CODE ABOVE ###\n",
    "\n",
    "    return tokens"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_doc_vector(tokens, vocab):\n",
    "    \"\"\"\n",
    "    Represent a document as a numerical vector of the length |vocab|\n",
    "    Args:\n",
    "        tokens (list): A list of tokens in the document\n",
    "        vocab (list): list of all possible unique tokens\n",
    "    Returns:\n",
    "        doc_vector (numpy array): a numerical vector representation of the document\n",
    "    \"\"\"\n",
    "    ### YOUR CODE BELOW ###\n",
    "    doc_vector = np.array([])\n",
    "    ### YOUR CODE ABOVE ###\n",
    "    return doc_vector"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cosine_similarity(vec1, vec2):\n",
    "    \"\"\"\n",
    "    Compute cosine similarity between two vectors of the same shape\n",
    "    Args:\n",
    "        vec1 (numpy array): The first vector of the shape (1, V)\n",
    "        vec1 (numpy array): The second vector of the shape (1, V)\n",
    "        \n",
    "    Returns:\n",
    "        similarity (float): The similarity between two vectors\n",
    "    \"\"\"\n",
    "    ### YOUR CODE BELOW ###\n",
    "    similarity = None\n",
    "    ### YOUR CODE ABOVE ###\n",
    "    \n",
    "    return similarity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def euclidean_distance(vec1, vec2):\n",
    "    \"\"\"\n",
    "    Compute euclidean distance between two vectors of the same shape\n",
    "    Args:\n",
    "        vec1 (numpy array): The first vector of the shape (1, V)\n",
    "        vec1 (numpy array): The second vector of the shape (1, V)\n",
    "        \n",
    "    Returns:\n",
    "        similarity (float): The L2 distance between two vectors\n",
    "    \"\"\"\n",
    "    ### YOUR CODE BELOW ###\n",
    "    distance = None\n",
    "    ### YOUR CODE ABOVE ###\n",
    "    return distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Tokenize\n",
    "doc1_tokens = tokenize_doc(doc1)\n",
    "doc2_tokens = tokenize_doc(doc2)\n",
    "\n",
    "# Construct voabulary\n",
    "vocab = sorted(list(set(doc1_tokens).union(set(doc2_tokens))))\n",
    "\n",
    "# Get numeric representations\n",
    "doc1_vector = get_doc_vector(doc1_tokens, vocab)\n",
    "doc2_vector = get_doc_vector(doc2_tokens, vocab)\n",
    "\n",
    "# Check the dimensions\n",
    "assert len(doc1_vector) == len(doc2_vector)\n",
    "\n",
    "# Compute the measures\n",
    "cos = cosine_similarity(doc1_vector, doc2_vector)\n",
    "dist = euclidean_distance(doc1_vector, doc2_vector)\n",
    "\n",
    "# Print the output\n",
    "print(\"Cosine similarity between the documents is {:.4f}\".format(cos))\n",
    "print(\"Euclidean distance between the documents is {:.4f}\".format(dist))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 2.2 $D_1$ and $D_2$ are merged into a single document. Consider all the lines in the resulting document.\n",
    "\n",
    "- What is the probability of the word “little” occuring in a given line?\n",
    "- What is the probability of the word “baby” occuring in a given line?\n",
    "- What is the pointwise mutual information (PMI) association score between “little” and “baby”?\n",
    "----\n",
    "\n",
    "To solve this problem, you will need to count both words in every line. The code that merges two documents, splits the result in separate lines, and tokenizes every line is written for you.\n",
    "\n",
    "__Instructions__:\n",
    "- Complete the code below to compute the probabilities\n",
    "- Use the obtained probabilities to compute the PMI score according to the definition of PMI:\n",
    "\n",
    "    $ \\text{PMI} =\\log_2{\\frac{P(x,y)}{P(x)P(y)}}$\n",
    "- Once the code is complete, run the cells below to output the answer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "doc_merged = doc1 + '\\n' + doc2\n",
    "doc_lines = [l.strip() for l in doc_merged.split('\\n')]\n",
    "doc_lines = [tokenize_doc(l) for l in doc_lines if l]\n",
    "\n",
    "### YOUR CODE BELOW ###\n",
    "probability_little = None\n",
    "probability_baby = None\n",
    "probability_little_baby = None\n",
    "pmi_little_baby = None\n",
    "### YOUR CODE ABOVE ###"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print('Probability of \"little\":', probability_little)\n",
    "print('Probability of \"baby\":', probability_baby)\n",
    "print('Probability of \"little baby\":', probability_little_baby)\n",
    "print('PMI association score between “little” and “baby” is {}'.format(pmi_little_baby))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 3. NLP problem setup\n",
    "Encyclopedia Britannica’s 3rd edition contains approximately ten thousand articles. After being scanned and converted to text using optical character recognition software, you are given a segment of it in a single text file. The file contains 100,000 text lines / 900,000 words / 300 articles, and has been manually marked up for article start and article finish. \n",
    "\n",
    "For your reference, an excerpt from the raw text and the marked text is given in the files `brit3-excerpt.txt` and `brit3-excerpt-marked.txt` correspondingly. Feel free to open these files in your favorite text editor and have a look.\n",
    "\n",
    "---\n",
    "__Instructions__:\n",
    "For each of the questions in each of the two problems below, give a 1-2 sentence answer. You don't have to write any code for this problem. Please fill out your answers in the cells below (as markdown text). Note that this problem does not have a single best answer. Use your imagination and be creative!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1 Imagine that you need to build a system that would split the given text into articles. Describe how you can cast this task as a classification problem:\n",
    "\n",
    "1. What are the instances that you will need to classify?\n",
    "2. What are the labels for the instances that your classification function will need to assign?\n",
    "3. Assuming you use 2/3 of your marked up data for training how many instances will you have in your training set?\n",
    "4. Give at leaves 5 examples of boolean features you might wish to include when building such a classifier."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__YOUR ANSWER HERE__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2 Now imagine that you need to build a system that would both split the text into articles and identify article titles. Again, assume that the titles have been marked in your training set. How can you cast this task as a classification problem? \n",
    "Please specify answers to (1), (2), (3), and (4) above for this new task."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__YOUR ANSWER HERE__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# PyTorch practice"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this part of homework you will be focusing on how to clean a given dataset and prepare it for training a skip-gram model.\n",
    "Skip-gram model is one of commonly used models to train [word embeddings](https://en.wikipedia.org/wiki/Word2vec#CBOW_and_skip_grams). Essentially, skip-gram model is a neural network that, given a target word, predicts one of the words from the context window (usually the context is 3-10 words on the left and 3-10 words on the right).\n",
    "\n",
    "This part of the homework consits of three main parts:\n",
    " 1. Data cleaning and preprocessing. In this part you will load the source corpus and tokenize it.\n",
    " 2. A vocabulary class that you need to implement. This class is essential in NLP, and it's a good idea to reuse it in your future work\n",
    " 3. Dataset class. This class is specific for the task at hand. In our case, it should handle the creating of the $(\\text{target_word},\\text{context_word})$ pairs\n",
    "\n",
    "\n",
    "We will train model on the `text8` corpus ([http://mattmahoney.net/dc/textdata.html](http://mattmahoney.net/dc/textdata.html)), which is already downladed and saved as the `text8.txt` file. This corpus consists of the first $10^9$ bytes of the English Wikipedia dump on Mar. 3, 2006.\n",
    "\n",
    "PyTorch provides a number of tools for data preparation that you will be using throughout the homework. Once you complete this homework, feel free to use (and change if needed) the implemented functions and classes in further assignments and in your projects.\n",
    "\n",
    "__Note__: In this part you will not implement the skip gram model itself - this is left for future homeworks"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Loading the corpus\n",
    "with open('text8.txt') as f:\n",
    "    data = f.read()\n",
    "\n",
    "print('There are', len(data), 'characters in total')\n",
    "print('The first 100 characters are:\\n', data[:100])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1. Dataset preprocessing\n",
    "We will start our workflow with parsing the input data file(-s). In general, depending on the problem you are solving and the input format of the given data, you might address text filtering differently. In our case, the text preprocessing stage will include the following steps:\n",
    "\n",
    "- Removing punctuation\n",
    "- Converting the input document to a seqence of tokens\n",
    "\n",
    "__Note__: In some cases it might be beneficial to lowercase the input data; however, our corpus here is already lowercased.\n",
    "\n",
    "----\n",
    "__Instructions__:\n",
    "\n",
    "- Complete the code in `preprocess` and the cells below to answer the questions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def preprocess(data):\n",
    "    \"\"\"\n",
    "    Args:\n",
    "        data (str):\n",
    "    Returns: a list of tokens\n",
    "\n",
    "    \"\"\"\n",
    "    ### YOUR CODE BELOW ###\n",
    "    tokens = []\n",
    "    ### YOUR CODE ABOVE ###\n",
    "\n",
    "    return tokens"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "tokens = preprocess(data)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1.1 How many tokens in total are in your input data?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "### YOUR CODE BELOW ###\n",
    "\n",
    "### YOUR CODE ABOVE ###"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1.2 What is the 64th token?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "### YOUR CODE BELOW ###\n",
    "\n",
    "### YOUR CODE ABOVE ###"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. Vocabulary\n",
    "Before the data gets loaded into the model, it has to be converted from raw text to a numeric representation. One way to achieve this is to introduce a token-to-id mapping. More specifically, you will implement a vocabulary class that maintains the mapping between tokens and their IDs, and that is able to flexibly add tokens and prune the vocabulary based on the token counts.\n",
    "\n",
    "When the input dataset is very large, vocabulary pruning is widely used in practice for more efficient memory usage.\n",
    "\n",
    "----\n",
    "\n",
    "__Instructions__:\n",
    "\n",
    "- Complete the code in `Vocabulary` class and the cells below to answer the questions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Vocabulary:\n",
    "    def __init__(self, special_tokens=None):\n",
    "        self.w2idx = {}\n",
    "        self.idx2w = {}\n",
    "        self.w2cnt = defaultdict(int)\n",
    "        self.special_tokens = special_tokens\n",
    "        if self.special_tokens is not None:\n",
    "            self.add_tokens(special_tokens)\n",
    "\n",
    "    def add_tokens(self, tokens):\n",
    "        for token in tokens:\n",
    "            ### YOUR CODE BELOW ###\n",
    "            pass\n",
    "            ### YOUR CODE ABOVE ###\n",
    "\n",
    "    def add_token(self, token):\n",
    "        ### YOUR CODE BELOW ###\n",
    "        pass\n",
    "        ### YOUR CODE ABOVE ###\n",
    "\n",
    "    def prune(self, min_cnt=2):\n",
    "        # do not forget to update the self.w2idx and self.idx2w dictionaries\n",
    "        ### YOUR CODE BELOW ###\n",
    "        pass\n",
    "        ### YOUR CODE ABOVE ###\n",
    "\n",
    "    def __contains__(self, item):\n",
    "        return item in self.w2idx\n",
    "    \n",
    "    def __getitem__(self, item):\n",
    "        if isinstance(item, str):\n",
    "            return self.w2idx[item]\n",
    "        elif isinstance(item , int):\n",
    "            return self.idx2w[item]\n",
    "        else:\n",
    "            raise TypeError(\"Supported indices are int and str\")\n",
    "    \n",
    "    def __len__(self):\n",
    "        return(len(self.w2idx))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "voc = Vocabulary(['UNK'])\n",
    "voc.add_tokens(tokens)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2.1 How many unique tokens are in your vocabulary?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "### YOUR CODE BELOW ###\n",
    "\n",
    "### YOUR CODE ABOVE ###"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2.2 What is the most frequent token? How many times does it appear in the dataset?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "### YOUR CODE BELOW ###\n",
    "\n",
    "### YOUR CODE ABOVE ###"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2.3 If you cut all the tokens that appear no more than 2 times in your dataset, how many unique tokens will your vocabulary contain?\n",
    "Hint: use the `prune` function here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "### YOUR CODE BELOW ###\n",
    "\n",
    "### YOUR CODE ABOVE ###"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3. Dataset\n",
    "The Dataset class provided by PyTorch is an abstract class representing any dataset used as input to a model. It is conveniently designed in a way that all the classes subclassing it would only have to override `__len__` and `__getitem__` methods. \n",
    "\n",
    "In this task you will subclass the Dataset class and implement your own `__len__` and `__getitem__` methods.\n",
    "Additionally, and specific to our case, you'll implememnt the `_generate_pairs` method, that will return all possible paris of $(\\text{target_word},\\text{context_word})$ given the input text.\n",
    "\n",
    "The goal of the `__getitem__` method is, given an index, to return the corresponding pair converted into the numerical representation using the vocab object.\n",
    "\n",
    "You might find it useful to have a look at the official [Data Loading and Processing Tutorial](https://pytorch.org/tutorials/beginner/data_loading_tutorial.html) on the PyTorch website.\n",
    "\n",
    "---\n",
    "\n",
    "__Instructions__:\n",
    "- Complete the code in `SkipGramDataset` class and the cells below to answer the questions.\n",
    "\n",
    "__Note__: since we pruned our vocabulary, we need to filter out pairs that are not not in our pruned vocabulary."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SkipGramDataset(Dataset):\n",
    "    def __init__(self, data, vocab, skip_window=3):\n",
    "        super().__init__()\n",
    "\n",
    "        self.vocab = vocab\n",
    "        self.data = data\n",
    "        self.skip_window = skip_window\n",
    "\n",
    "        self.pairs = self._generate_pairs(data, skip_window)\n",
    "\n",
    "    def _generate_pairs(self, data, skip_window):\n",
    "        \"\"\"\n",
    "        Args: input data (a list of tokens) and the window size\n",
    "        Returns: all possible pairs for the SkipGram mode\n",
    "        \"\"\"\n",
    "        pairs = []\n",
    "\n",
    "        # do not forget to filter out pairs with out-of-vocabulary tokens \n",
    "        ### YOUR CODE BELOW ###\n",
    "\n",
    "        ### YOUR CODE ABOVE ###\n",
    "                \n",
    "        return pairs\n",
    "\n",
    "\n",
    "    def __getitem__(self, idx):\n",
    "        \"\"\"\n",
    "        Args:\n",
    "            idx\n",
    "        Returns:\n",
    "\n",
    "        \"\"\"\n",
    "        ### YOUR CODE BELOW ###\n",
    "        \n",
    "        ### YOUR CODE ABOVE ###\n",
    "\n",
    "        return pair\n",
    "\n",
    "    def __len__(self):\n",
    "        \"\"\"\n",
    "        Returns\n",
    "        \"\"\"\n",
    "        return len(self.pairs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 3.1 Initialize your `SkipGramDataset` class using the data and the vocab objects with `skip_window=2`. Print out the 43rd pair and 43rd item in the dataset."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "### YOUR CODE BELOW ###\n",
    "\n",
    "### YOUR CODE ABOVE ###"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 3.2 What is the total length of the dataset (that is, the total number of pairs)?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "### YOUR CODE BELOW ###\n",
    "\n",
    "### YOUR CODE ABOVE ###"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 3.3 Print out the 43rd pair and 43rd item in the dataset."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "### YOUR CODE BELOW ###\n",
    "\n",
    "### YOUR CODE ABOVE ###"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4. DataLoader\n",
    "DataLoader is another useful class of PyTorch that combines a dataset and a sampler, and provides single- or multi-process iterators over the dataset. The goal of data loader is to create batches of training examples for the network by sampling the dataset and combining the sampled items into batches. \n",
    "\n",
    "__Instructions__:\n",
    "- Complete the code in in the cells below to answer the questions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dataloader = DataLoader(dataset, shuffle=True, batch_size=20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 4.1 How many batches of size 20 would you need to fit all training examples in the dataset?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "### YOUR CODE BELOW ###\n",
    "\n",
    "### YOUR CODE ABOVE ###"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 4.2 Verify the number above by using the `len` function on the dataloader object"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "### YOUR CODE BELOW ###\n",
    "\n",
    "### YOUR CODE ABOVE ###"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, after you have a dataloader, you can iterate over it to dynamically create batches of the traning samples. An example of a training loop is given below:\n",
    "```python\n",
    "for epoch in range(100):\n",
    "    for i, batch in enumerate(dataloader):\n",
    "        x, y = batch\n",
    "\n",
    "        # use x, y to train the model\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Let's see what's inside a batch\n",
    "batch = next(iter(dataloader))\n",
    "print(\"The batch size is {}\".format(len(batch)))\n",
    "pair_target, pair_context = batch\n",
    "print(\"The batch of target word indices is: \\n{}\".format(pair_target))\n",
    "print(\"The batch of context word indices is: \\n{}\".format(pair_context))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.6.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}