english_notebooks/Ngrams-Eng.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Befor going through the notebook you should read first 7 pages of - https://web.stanford.edu/~jurafsky/slp3/3.pdf"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Language modelling"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Language modelling is basically just assigning probabilities to words. On its own LM is not very useful, but it can be applied to almost any other NLP task. Recent progress in NLP is in large part driven by language models (BERT, ELMO, GPT-2)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Language modelling is a complicated topic, so we go through it gradually. In this notebook, we'll look at the basics."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's take two big books."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['austen-emma.txt',\n",
       " 'austen-persuasion.txt',\n",
       " 'austen-sense.txt',\n",
       " 'bible-kjv.txt',\n",
       " 'blake-poems.txt',\n",
       " 'bryant-stories.txt',\n",
       " 'burgess-busterbrown.txt',\n",
       " 'carroll-alice.txt',\n",
       " 'chesterton-ball.txt',\n",
       " 'chesterton-brown.txt',\n",
       " 'chesterton-thursday.txt',\n",
       " 'edgeworth-parents.txt',\n",
       " 'melville-moby_dick.txt',\n",
       " 'milton-paradise.txt',\n",
       " 'shakespeare-caesar.txt',\n",
       " 'shakespeare-hamlet.txt',\n",
       " 'shakespeare-macbeth.txt',\n",
       " 'whitman-leaves.txt']"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# NLTK includes a small selection of texts from the Project Gutenberg electronic text archive, \n",
    "# which contains some 25,000 free electronic books, hosted at http://www.gutenberg.org/. \n",
    "import nltk\n",
    "nltk.download('gutenberg')\n",
    "nltk.corpus.gutenberg.fileids()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "emma = nltk.corpus.gutenberg.raw('austen-emma.txt')\n",
    "moby = nltk.corpus.gutenberg.raw('melville-moby_dick.txt')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Анна Каренина немного больше."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Length of Emma - 887071\n",
      "Length of Moby Dick -  1242990\n"
     ]
    }
   ],
   "source": [
    "print(\"Length of Emma -\", len(emma))\n",
    "print(\"Length of Moby Dick - \", len(moby))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Simple normalization pipeline. You should understand what it does by now"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "from string import punctuation\n",
    "import numpy as np\n",
    "\n",
    "def normalize(text):\n",
    "    normalized_text = [(word.strip(punctuation)) for word \\\n",
    "                                                            in text.lower().split()]\n",
    "    normalized_text = [word for word in normalized_text if word]\n",
    "    return normalized_text\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can compare two texts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "norm_emma = normalize(emma)\n",
    "norm_moby = normalize(moby)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Length of Emma in tokens - 158131\n",
      "Length of Moby Dick in tokens -  212013\n"
     ]
    }
   ],
   "source": [
    "print(\"Length of Emma in tokens -\", len(norm_emma))\n",
    "print(\"Length of Moby Dick in tokens - \", len(norm_moby))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['emma', 'by', 'jane', 'austen', '1816', 'volume', 'i', 'chapter', 'i', 'emma']"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "norm_emma[:10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Unique tokens in Emma - 9460\n",
      "Unique tokens in Moby Dick -  20233\n"
     ]
    }
   ],
   "source": [
    "print(\"Unique tokens in Emma -\", len(set(norm_emma)))\n",
    "print(\"Unique tokens in Moby Dick - \", len(set(norm_moby)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's compute word frequencies"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "vocab_emma = Counter(norm_emma)\n",
    "vocab_moby = Counter(norm_moby)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('to', 5149),\n",
       " ('the', 5146),\n",
       " ('and', 4613),\n",
       " ('of', 4274),\n",
       " ('a', 3073),\n",
       " ('i', 2968),\n",
       " ('her', 2417),\n",
       " ('it', 2400),\n",
       " ('was', 2376),\n",
       " ('she', 2278)]"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "vocab_emma.most_common(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('the', 14320),\n",
       " ('of', 6578),\n",
       " ('and', 6362),\n",
       " ('a', 4628),\n",
       " ('to', 4577),\n",
       " ('in', 4143),\n",
       " ('that', 2940),\n",
       " ('his', 2520),\n",
       " ('it', 2368),\n",
       " ('i', 1943)]"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "vocab_moby.most_common(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we devide each frequency by the size of the corpus (total number of tokens) we'll get word probabilities!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('to', 0.03256161031043881),\n",
       " ('the', 0.03254263869829445),\n",
       " ('and', 0.029172015607312925),\n",
       " ('of', 0.027028223435000095),\n",
       " ('a', 0.019433254706540778),\n",
       " ('i', 0.018769248281488134),\n",
       " ('her', 0.015284795517640438),\n",
       " ('it', 0.015177289715489057),\n",
       " ('was', 0.015025516818334165),\n",
       " ('she', 0.01440577748828503),\n",
       " ('in', 0.013577350424647918),\n",
       " ('not', 0.013406605915348667),\n",
       " ('be', 0.012426405954556664),\n",
       " ('you', 0.01212918403096167),\n",
       " ('that', 0.011123688587310521),\n",
       " ('he', 0.011111040845880946),\n",
       " ('had', 0.010232022816525538),\n",
       " ('as', 0.00904945899286035),\n",
       " ('have', 0.008322213860659834),\n",
       " ('for', 0.008271622894941535)]"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "probas_emma = Counter({word:c/len(norm_emma) for word, c in vocab_emma.items()})\n",
    "probas_emma.most_common(20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('the', 0.06754302802186658),\n",
       " ('of', 0.03102639932456972),\n",
       " ('and', 0.03000759387396056),\n",
       " ('a', 0.021828850117681462),\n",
       " ('to', 0.02158829883073208),\n",
       " ('in', 0.01954125454571182),\n",
       " ('that', 0.01386707418884691),\n",
       " ('his', 0.01188606359044021),\n",
       " ('it', 0.011169126421493022),\n",
       " ('i', 0.009164532363581479),\n",
       " ('but', 0.008376844816119767),\n",
       " ('he', 0.008240060750991684),\n",
       " ('with', 0.00811271006966554),\n",
       " ('as', 0.00810799337776457),\n",
       " ('is', 0.008046676383051983),\n",
       " ('was', 0.007711791258083231),\n",
       " ('for', 0.007537273657747402),\n",
       " ('all', 0.006957120553928297),\n",
       " ('this', 0.006424134369118875),\n",
       " ('at', 0.006178866390268521)]"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "probas_moby = Counter({word:c/len(norm_moby) for word, c in vocab_moby.items()})\n",
    "probas_moby.most_common(20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These probabilities can be used to directly compare the usage of word by different authors or we can try to predict who would more likely say some phrase?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [],
   "source": [
    "phrase = 'I hate that whale'\n",
    "\n",
    "prob = Counter({'emma':0, 'moby':0})\n",
    "\n",
    "for word in normalize(phrase):\n",
    "    # logarithm is often applied to probabilities\n",
    "    # when we multiply small numbers (like probabilities) we can quickly get too many zeros\n",
    "    # addition of logarithms is equivalent to multiplying probabilities\n",
    "    \n",
    "    prob['emma'] += np.log(probas_emma.get(word, 0.00001)) # we need small probas in case the word is missing\n",
    "    prob['moby'] += np.log(probas_moby.get(word, 0.00001))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('moby', -24.559352967277015), ('emma', -30.57202400204973)]"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# the bigger the result (closer to 0) the more probable\n",
    "prob.most_common()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here we just multiplied the probabilities of individual words. It is equivalent to saying that every word in a text is selected independently. Which is obviously not true."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Actually we need to use the formula of [total probability](https://en.wikipedia.org/wiki/Law_of_total_probability)\n",
    "The problem is - we can't compute probabilities for sequences we haven't seen in the corpus. And the longer the sequence the less likely it is that we saw the sequence before. \n",
    "\n",
    "To overcome this, we can use [Markov assumption](https://en.wikipedia.org/wiki/Markov_property) and approximate the probability of a sequence as a product of bigram probabilities. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First, we need to get bigram frequencies."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [],
   "source": [
    "from nltk.tokenize import sent_tokenize\n",
    "def ngrammer(tokens, n=2):\n",
    "    ngrams = []\n",
    "    for i in range(0,len(tokens)-n+1):\n",
    "        ngrams.append(' '.join(tokens[i:i+n]))\n",
    "    return ngrams"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['emma', 'by', 'jane', 'austen', '1816', 'volume', 'i', 'chapter', 'i', 'emma']"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "norm_emma[:10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['emma by',\n",
       " 'by jane',\n",
       " 'jane austen',\n",
       " 'austen 1816',\n",
       " '1816 volume',\n",
       " 'volume i',\n",
       " 'i chapter',\n",
       " 'chapter i',\n",
       " 'i emma']"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ngrammer(norm_emma[:10])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We need to add \\< start \\> to every sentence to make proper probability distribution and also to be able to start a sequence if we want to generate.\n",
    "\n",
    "To be able to stop we need  \\< end \\> to every sentence"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "sentences_emma = [['<start>'] + normalize(text) + ['<end>'] for text in sent_tokenize(emma)]\n",
    "sentences_moby = [['<start>'] + normalize(text) + ['<end>'] for text in sent_tokenize(moby)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [],
   "source": [
    "unigrams_emma = Counter()\n",
    "bigrams_emma = Counter()\n",
    "\n",
    "for sentence in sentences_emma:\n",
    "    unigrams_emma.update(sentence)\n",
    "    bigrams_emma.update(ngrammer(sentence))\n",
    "\n",
    "\n",
    "unigrams_moby = Counter()\n",
    "bigrams_moby = Counter()\n",
    "\n",
    "for sentence in sentences_moby:\n",
    "    unigrams_moby.update(sentence)\n",
    "    bigrams_moby.update(ngrammer(sentence))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "9436"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(unigrams_emma)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('<start> i', 871),\n",
       " ('to be', 602),\n",
       " ('of the', 559),\n",
       " ('<start> she', 505),\n",
       " ('in the', 441),\n",
       " ('it was', 418),\n",
       " ('<start> he', 395),\n",
       " ('i am', 363),\n",
       " ('<start> it', 339),\n",
       " ('she had', 322)]"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bigrams_emma.most_common(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('of the', 1879),\n",
       " ('in the', 1176),\n",
       " ('to the', 726),\n",
       " ('<start> but', 704),\n",
       " ('<start> the', 545),\n",
       " ('from the', 440),\n",
       " ('<start> and', 406),\n",
       " ('<start> i', 396),\n",
       " ('of his', 371),\n",
       " ('and the', 368)]"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bigrams_moby.most_common(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The probality of bigram more formally is the probability of word2 given word1. We can compute it by deviding the number of occurences of word2 and word1 together by the number of occurences of word1 -  \n",
    "**p(word1 word2)** = **(word1 and word2)/word1**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [],
   "source": [
    "phrase = 'If I loved you less, I might be able to talk about it more' #emma quote\n",
    "# phrase = 'For there are devils in the deep, but worst are the ones we make.' #moby dick quote\n",
    "\n",
    "prob = Counter()\n",
    "for ngram in ngrammer(['<start>'] + normalize(phrase) + ['<end>']):\n",
    "    word1, word2 = ngram.split()\n",
    "    if word1 in unigrams_emma and ngram in bigrams_emma:\n",
    "        prob['emma'] += np.log(bigrams_emma[ngram]/unigrams_emma[word1])\n",
    "    else:\n",
    "        prob['emma'] += -10 # we need small proba in case the word is missing\n",
    "    if word1 in unigrams_moby and ngram in bigrams_moby:\n",
    "        prob['moby'] += np.log(bigrams_moby[ngram]/unigrams_moby[word1])\n",
    "    else:\n",
    "        prob['moby'] += -10\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('emma', -58.08141178760031), ('moby', -83.59821440802531)]"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prob.most_common()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using those probabilities we can try to generate a text in Austen style."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [],
   "source": [
    "# we build a matrix of probabilities\n",
    "# ij-element in a matrix is a probability of (word_i, word_j)\n",
    "\n",
    "matrix_emma = np.zeros((len(unigrams_emma), \n",
    "                   len(unigrams_emma)))\n",
    "\n",
    "# we create a dictionary of word-index and index-word mapping\n",
    "# because we use indecies in matrix and words in sentences\n",
    "id2word_emma = list(unigrams_emma)\n",
    "word2id_emma = {word:i for i, word in enumerate(id2word_emma)}\n",
    "\n",
    "\n",
    "for ngram in bigrams_emma:\n",
    "    word1, word2 = ngram.split()\n",
    "    matrix_emma[word2id_emma[word1]][word2id_emma[word2]] =  (bigrams_emma[ngram]/\n",
    "                                                                     unigrams_emma[word1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "matrix_moby = np.zeros((len(unigrams_moby), \n",
    "                   len(unigrams_moby)))\n",
    "\n",
    "id2word_moby = list(unigrams_moby)\n",
    "word2id_moby = {word:i for i, word in enumerate(id2word_moby)}\n",
    "\n",
    "\n",
    "\n",
    "for ngram in bigrams_moby:\n",
    "    word1, word2 = ngram.split()\n",
    "    matrix_moby[word2id_moby[word1]][word2id_moby[word2]] =  (bigrams_moby[ngram]/\n",
    "                                                                     unigrams_moby[word1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**This matrix of probabilities is a bigram language model**. We can write a simple function that will generate N words using this language model."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### The generation process is like this:  \n",
    "----\n",
    "1) we start with \\< start \\> token  \n",
    "2) we use the index of \\< start \\> to get the probabilites of the next words  \n",
    "3) we use np.random.choice to select the next word according to the probabilities  \n",
    "4) we add the chosen word to the text and use it to generate the next word  \n",
    "5) when we see \\< end >\\ token we stop or continue from the beginning  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def generate(matrix, id2word, word2id, n=100, start='<start>'):\n",
    "    text = []\n",
    "    current_idx = word2id[start]\n",
    "    \n",
    "    for i in range(n):\n",
    "        \n",
    "        chosen = np.random.choice(matrix.shape[1], p=matrix[current_idx])\n",
    "#       try uncommenting the line below to see why we need np.random.choice\n",
    "#         chosen = matrix[current_idx].argmax() # it just selects most probable word\n",
    "\n",
    "        text.append(id2word[chosen])\n",
    "        \n",
    "        if id2word[chosen] == '<end>':\n",
    "            chosen = word2id['<start>']\n",
    "        current_idx = chosen\n",
    "    \n",
    "    return ' '.join(text)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "but i love must be danced would speak of her husband and miss fairfax \n",
      " it will turn out in poor comfort but a pen in my accents swell to enscombe \n",
      " weston.--so it darted through \n",
      " bought at home he was very different homes and was as to see them emma's little time since we never had so much benefit and expressions but certainly shews it in confessing exactly \n",
      " the want only to sit down the liveliest objects she that could answer written enough broad neat and this being affected by her tongue \n",
      " no,\"--he gravely \n",
      " i\n"
     ]
    }
   ],
   "source": [
    "print(generate(matrix_emma, id2word_emma, word2id_emma).replace('<end>', '\\n'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "i don't you are part of uncommon bulk \n",
      " it can't remember he can hit aright this part of that the driving on the middle-watch a world \n",
      " turn to!--i make much the great sperm whales \n",
      " and fish seen to on the boats are absolutely paints like old second was examined the streets of instantaneous violent gaspings and informed nantucketers born of the widely-separated ships made the binnacle slipped my dear domestic peculiarity on the waters near them daggoo \n",
      " look so ahab stayed in the many of all hard \n",
      " coming \n",
      " i cherished no telling said excitedly\n"
     ]
    }
   ],
   "source": [
    "print(generate(matrix_moby, id2word_moby, word2id_moby).replace('<end>', '\\n'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Homework (Task 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Implement a trigram language model, generate some texts and compare it to the bigram language model we wrote above. Which one gives better texts?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Use the code above as a starting point. You don't really need to change much, but it might be difficult to figure out. Read Jurasky carefully to get a better undestanding. And feel free to ask me any questions. \n",
    "\n",
    "You can use other corpus if you want.   \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Hints**:  \n",
    "you'll need two start-tags in trigram language model,   \n",
    "use bigrams as rows in the matrix and unigrams as columns,   \n",
    "if the text you generated is just randow words - something is wrong"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---------------------------"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Collocation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "Collocations are word combinations that occur regularly. If we want to find good collocations we can't just use word probabilities because they only show how the word2 is likely after word1. If word2 only occurs after word1 it is a good collocation, but it can be rare and its probability will be low."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There can be many ways of scoring collocations. The most common one is [PMI](https://en.wikipedia.org/wiki/Pointwise_mutual_information)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The formula for PMI is **p(ab)/p(a)*p(b)** Let's try it out on our texts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter, defaultdict\n",
    "import numpy as np\n",
    "from nltk.corpus import stopwords\n",
    "from string import punctuation\n",
    "stops = set(stopwords.words('english'))\n",
    "\n",
    "def normalize(text):\n",
    "    normalized_text = [word.strip(punctuation) for word \\\n",
    "                                                            in text.lower().split()]\n",
    "    normalized_text = [word for word in normalized_text if word not in stops]\n",
    "    return normalized_text\n",
    "\n",
    "\n",
    "def ngrammer(tokens, n=2):\n",
    "    ngrams = []\n",
    "    for i in range(0,len(tokens)-n+1):\n",
    "        ngrams.append(' '.join(tokens[i:i+n]))\n",
    "    return ngrams\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Preprocessing is the same"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "sentences_emma =  [normalize(text) for text in sent_tokenize(emma)]\n",
    "sentences_moby =  [normalize(text) for text in sent_tokenize(moby)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [],
   "source": [
    "word_counter = Counter()\n",
    "\n",
    "for text in sentences_emma:\n",
    "    word_counter.update(ngrammer(text, n=2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('mr knightley', 242),\n",
       " ('mrs weston', 217),\n",
       " ('mr elton', 174),\n",
       " ('miss woodhouse', 150),\n",
       " ('mr weston', 136),\n",
       " ('frank churchill', 123),\n",
       " ('every thing', 119),\n",
       " ('mrs elton', 115),\n",
       " ('miss fairfax', 105),\n",
       " ('mr woodhouse', 104),\n",
       " ('miss bates', 97),\n",
       " ('jane fairfax', 90),\n",
       " ('every body', 86),\n",
       " ('young man', 75),\n",
       " ('great deal', 63)]"
      ]
     },
     "execution_count": 79,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "word_counter.most_common(15)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can use raw counts instead of probabilities. The results we'll be relatively the same."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [],
   "source": [
    "def scorer_pmi(word_count_a, word_count_b, bigram_count):\n",
    "    try:\n",
    "        score = bigram_count/((word_count_a*word_count_b))\n",
    "    \n",
    "    except ZeroDivisionError:\n",
    "        return 0\n",
    "    \n",
    "    return score"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'll make a function to collect unigrams and bigrams"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [],
   "source": [
    "def collect_stats(texts):\n",
    "    \n",
    "    unigrams = Counter()\n",
    "    bigrams = Counter()\n",
    "    \n",
    "    for text in texts:\n",
    "        unigrams.update(text)\n",
    "        bigrams.update(ngrammer(text, 2))\n",
    "    \n",
    "    return unigrams, bigrams"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And also a function that will score every bigram we collect."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 158,
   "metadata": {},
   "outputs": [],
   "source": [
    "def score_bigrams(unigrams, bigrams, scorer, threshold=-100000):\n",
    "    \n",
    "    bigram2score = Counter()\n",
    "    len_vocab = len(unigrams)\n",
    "    for bigram in bigrams:\n",
    "        score = scorer(unigrams[bigram[0]], unigrams[bigram[1]], \n",
    "                       bigrams[bigram])\n",
    "        \n",
    "        ## if PMI is bigger than the threshold we add to the result\n",
    "        if score > threshold:\n",
    "            bigram2score[bigram] = score\n",
    "    \n",
    "    return bigram2score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {},
   "outputs": [],
   "source": [
    "unigrams, bigrams = collect_stats(sentences_moby)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {},
   "outputs": [],
   "source": [
    "bigram2score = score_bigrams(unigrams, bigrams, scorer_pmi)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here we rank bigrams by their PMI scores"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('let us', 12.5),\n",
       " ('new bedford', 8.5),\n",
       " ('never mind', 8.5),\n",
       " ('closed eyes', 5.0),\n",
       " ('chief mate', 5.0),\n",
       " ('never heard', 4.0),\n",
       " ('next morning', 3.5),\n",
       " ('new england', 3.0),\n",
       " ('new zealand', 3.0),\n",
       " ('centuries ago', 3.0),\n",
       " ('let go', 3.0),\n",
       " ('next day', 3.0),\n",
       " ('never yet', 3.0),\n",
       " ('clear spirit', 3.0),\n",
       " ('new york', 2.5)]"
      ]
     },
     "execution_count": 111,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bigram2score.most_common(15)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also add minimum bigram count to the function, so the word combination that occurred only once would not be on the top."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "metadata": {},
   "outputs": [],
   "source": [
    "def scorer_pmi(word_count_a, word_count_b, bigram_count, min_count=1):\n",
    "    try:\n",
    "        score = ((bigram_count - min_count) / ((word_count_a * word_count_b)))\n",
    "    except ZeroDivisionError:\n",
    "        return 0\n",
    "    \n",
    "    return score\n",
    "def score_bigrams(unigrams, bigrams, scorer, threshold=-100000, min_count=1):\n",
    "    \n",
    "    bigram2score = Counter()\n",
    "    len_vocab = len(unigrams)\n",
    "    for bigram in bigrams:\n",
    "        score = scorer(unigrams[bigram[0]], unigrams[bigram[1]], \n",
    "                       bigrams[bigram], min_count)\n",
    "        \n",
    "        \n",
    "        if score > threshold:\n",
    "            bigram2score[bigram] = score\n",
    "    \n",
    "    return bigram2score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "metadata": {},
   "outputs": [],
   "source": [
    "bigram2score = score_bigrams(unigrams, bigrams, scorer_pmi, min_count=10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 114,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('let us', 8.0),\n",
       " ('new bedford', 4.0),\n",
       " ('never mind', 4.0),\n",
       " ('every one', 1.2),\n",
       " ('chief mate', 0.5),\n",
       " ('ever since', 0.3),\n",
       " ('every way', 0.1),\n",
       " ('moby dick', 0),\n",
       " ('dick herman', 0),\n",
       " ('melville 1851', 0),\n",
       " ('supplied late', 0),\n",
       " ('late consumptive', 0),\n",
       " ('consumptive usher', 0),\n",
       " ('usher grammar', 0),\n",
       " ('grammar school', 0)]"
      ]
     },
     "execution_count": 114,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bigram2score.most_common(15)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can read about other metrics for scoring collocations here:\n",
    "\n",
    "http://www.scielo.org.mx/scielo.php?script=sci_arttext&pid=S1405-55462016000300327#t1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---------------------"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are some existing tools to collect collocations from the corpus. Gensim has one."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "metadata": {},
   "outputs": [],
   "source": [
    "import gensim"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "metadata": {},
   "outputs": [],
   "source": [
    "sentences = []\n",
    "for sent in sent_tokenize(moby):\n",
    "    sentences.append(normalize(sent))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 156,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['supplied',\n",
       " 'late',\n",
       " 'consumptive',\n",
       " 'usher',\n",
       " 'grammar',\n",
       " 'school',\n",
       " 'pale',\n",
       " 'usher--threadbare',\n",
       " 'coat',\n",
       " 'heart',\n",
       " 'body',\n",
       " 'brain',\n",
       " 'see']"
      ]
     },
     "execution_count": 156,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sentences[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 141,
   "metadata": {},
   "outputs": [],
   "source": [
    "# train\n",
    "# here npmi is used to score bigrams\n",
    "# it is similar to pmi, but is from -1 to 1\n",
    "ph = gensim.models.Phrases(sentences, min_count=1, threshold=-1, scoring='npmi')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 142,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['take_hand',\n",
       " 'school_others',\n",
       " 'teach_name',\n",
       " 'whale-fish_called',\n",
       " 'tongue_leaving',\n",
       " 'ignorance_letter',\n",
       " 'h_almost',\n",
       " 'alone_maketh',\n",
       " 'signification_word',\n",
       " 'deliver_true']"
      ]
     },
     "execution_count": 142,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# transforming text\n",
    "ph[list(sentences[4])]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 147,
   "metadata": {},
   "outputs": [],
   "source": [
    "# we can apply Phraser to the bigrammed text\n",
    "ph2 = gensim.models.Phrases(ph[sentences], min_count=1, threshold=-1, scoring='npmi')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 149,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['take_hand_school_others',\n",
       " 'teach_name_whale-fish_called',\n",
       " 'tongue_leaving_ignorance_letter',\n",
       " 'h_almost_alone_maketh',\n",
       " 'signification_word_deliver_true']"
      ]
     },
     "execution_count": 149,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# and then we can applied both Phrases to the text sequentially and get 4-grams \n",
    "ph2[ph[sentences[4]]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nltk also has ngram scorer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 150,
   "metadata": {},
   "outputs": [],
   "source": [
    "import nltk\n",
    "from nltk.collocations import *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 151,
   "metadata": {},
   "outputs": [],
   "source": [
    "bigram_measures = nltk.collocations.BigramAssocMeasures()\n",
    "trigram_measures = nltk.collocations.TrigramAssocMeasures()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 152,
   "metadata": {},
   "outputs": [],
   "source": [
    "finder2 = BigramCollocationFinder.from_documents(sentences)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 153,
   "metadata": {},
   "outputs": [],
   "source": [
    "finder3 = TrigramCollocationFinder.from_documents(sentences)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 154,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('moby', 'dick'),\n",
       " ('sperm', 'whale'),\n",
       " ('white', 'whale'),\n",
       " ('captain', 'ahab'),\n",
       " ('old', 'man'),\n",
       " ('sperm', \"whale's\"),\n",
       " ('new', 'bedford'),\n",
       " ('captain', 'peleg'),\n",
       " ('mr', 'starbuck'),\n",
       " ('cape', 'horn'),\n",
       " ('aye', 'aye'),\n",
       " ('right', 'whale'),\n",
       " ('cried', 'ahab'),\n",
       " ('thou', 'art'),\n",
       " ('let', 'us'),\n",
       " ('years', 'ago'),\n",
       " (\"d'ye\", 'see'),\n",
       " ('lower', 'jaw'),\n",
       " ('father', 'mapple'),\n",
       " ('ivory', 'leg')]"
      ]
     },
     "execution_count": 154,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "finder2.nbest(bigram_measures.likelihood_ratio, 20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 155,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('great', 'sperm', 'whale'),\n",
       " ('sperm', \"whale's\", 'head'),\n",
       " ('every', 'one', 'knows'),\n",
       " ('seen', 'white', 'whale'),\n",
       " ('cape', 'good', 'hope'),\n",
       " ('seven', 'hundred', 'seventy-seventh'),\n",
       " ('greenland', 'right', 'whale'),\n",
       " ('hast', 'seen', 'white'),\n",
       " ('right', \"whale's\", 'head'),\n",
       " ('sperm', 'whale', 'fishery'),\n",
       " ('would', 'almost', 'thought'),\n",
       " ('captain', 'ahab', 'said'),\n",
       " ('chase', 'moby', 'dick'),\n",
       " ('even', 'present', 'day'),\n",
       " ('god', 'bless', 'ye'),\n",
       " ('old', 'manx', 'sailor'),\n",
       " ('round', 'cape', 'horn'),\n",
       " ('sleep', 'two', 'bed'),\n",
       " ('stubb', 'second', 'mate'),\n",
       " ('thou', 'clear', 'spirit')]"
      ]
     },
     "execution_count": 155,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "finder3.nbest(trigram_measures.raw_freq, 20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Homework (Task 2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Implement a simple version of Byte-pair-encoding (see first seminar) using gensim.models.Phrases.\n",
    "\n",
    "Apply gensim.models.Phrases to character sequences instead of word sequences (sentences). Train at least 3 Phrases sequentially. As a result you should get whole words or long character ngrams. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 160,
   "metadata": {},
   "outputs": [],
   "source": [
    "# when you apply you phrasers to the text \n",
    "p3[p2[p[text]]] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# you should get something like\n",
    "['s_o_m', 'e', 'r_a', 'n_d_o_m', 't_e_x_t', 'h_e', 'r', 'e']"
   ]
  }
 ],
 "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}