laplace-smoothing.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**NOTE:** The first three steps will be the same as in the baseline model."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import nltk\n",
    "import utils\n",
    "import random\n",
    "from pomegranate import State, HiddenMarkovModel, DiscreteDistribution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 1\n",
    "\n",
    "Download the brown data set and split it into a train / test with a ratio of 0.8 / 0.2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[nltk_data] Downloading package brown to /root/nltk_data...\n",
      "[nltk_data]   Package brown is already up-to-date!\n",
      "Train 45872\n",
      "Test 11468\n"
     ]
    }
   ],
   "source": [
    "nltk.download('brown')\n",
    "\n",
    "corpus = list(nltk.corpus.brown.tagged_sents())\n",
    "\n",
    "random.seed(42)\n",
    "random.shuffle(corpus)\n",
    "\n",
    "split = int(0.8 * len(corpus))\n",
    "\n",
    "train = corpus[:split]\n",
    "test = corpus[split:]\n",
    "\n",
    "print('Train', len(train))\n",
    "print('Test', len(test))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 2\n",
    "\n",
    "Originally tagged sentences represented as sequences of tuple, i.e. (word, tag). We need to rearrange data in order to match to default format from the project \"Part of Speech Tagging\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[('He', 'PPS'), ('let', 'VBD'), ('her', 'PPO'), ('tell', 'VB'), ('him', 'PPO'), ('all', 'ABN'), ('about', 'IN'), ('the', 'AT'), ('church', 'NN'), ('.', '.')]\n"
     ]
    }
   ],
   "source": [
    "print(train[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "train_x, train_y, train_words, train_tagset = utils.rearrange_data(train)\n",
    "test_x, test_y, test_words, test_tagset = utils.rearrange_data(test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['He', 'let', 'her', 'tell', 'him', 'all', 'about', 'the', 'church', '.']\n",
      "['PPS', 'VBD', 'PPO', 'VB', 'PPO', 'ABN', 'IN', 'AT', 'NN', '.']\n"
     ]
    }
   ],
   "source": [
    "print(train_x[0])\n",
    "print(train_y[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Train words 50630 tags 450\n",
      "Unknown test words 5427 tags 22\n"
     ]
    }
   ],
   "source": [
    "print('Train words', len(train_words), 'tags', len(train_tagset))\n",
    "print('Unknown test words', len(test_words.difference(train_words)), 'tags', len(test_tagset.difference(train_tagset)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 3 \n",
    "\n",
    "Accumulate statistics of the training data using the functions from the regular steps of the mentioned project."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "emission_counts = utils.pair_counts(train_y, train_x)\n",
    "tag_unigrams = utils.unigram_counts(train_y)\n",
    "tag_bigrams = utils.bigram_counts(train_y)\n",
    "tag_starts = utils.starting_counts(train_y)\n",
    "tag_ends = utils.ending_counts(train_y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 3.1\n",
    "\n",
    "I'll smoothe only transition probability from tag to tag, and also add the unknown transitions, which tags exists in the training data. To do this efficiently, I first find the unknown bigrams from the test data. It allows me to not add unused transition into the model."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "tag_bigrams_test = utils.bigram_counts(test_y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 4\n",
    "\n",
    "Now, create the model with laplace smoothing."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Extend transition model 7552 by 458\n",
      "Edges 8276\n"
     ]
    }
   ],
   "source": [
    "model = HiddenMarkovModel(name=\"brown-smooth-hmm-tagger\")\n",
    "\n",
    "states = dict()\n",
    "for tag, words in emission_counts.items():\n",
    "    n = tag_unigrams[tag]\n",
    "    assert n == sum(words.values())\n",
    "    probs = {w:c / n for w, c in words.items()}\n",
    "    emissions = DiscreteDistribution(probs)\n",
    "    state = State(emissions, name=tag)\n",
    "    model.add_states(state)\n",
    "    states[tag] = state\n",
    "\n",
    "n = sum(tag_starts.values())\n",
    "for tag, counts in tag_starts.items():\n",
    "    model.add_transition(model.start, states[tag], counts / n)\n",
    "\n",
    "for (tag1, tag2), counts in tag_bigrams.items():\n",
    "    nominator = counts + 1\n",
    "    denominator = tag_unigrams[tag1] + len(train_tagset)\n",
    "    model.add_transition(states[tag1], states[tag2], nominator / denominator)\n",
    "\n",
    "for tag, counts in tag_ends.items():\n",
    "    model.add_transition(states[tag], model.end, counts / tag_unigrams[tag])\n",
    "\n",
    "# NOTE: counts statistics from the test set is not used\n",
    "\n",
    "new_bigrams = 0\n",
    "for (tag1, tag2), counts in tag_bigrams_test.items():\n",
    "    if (tag1, tag2) in tag_bigrams:\n",
    "        continue\n",
    "    if tag1 not in states or tag2 not in states:\n",
    "        continue\n",
    "    denominator = len(train_tagset)\n",
    "    if tag1 in tag_unigrams:\n",
    "        denominator += tag_unigrams[tag1]\n",
    "    model.add_transition(states[tag1], states[tag2], 1 / denominator)\n",
    "    new_bigrams += 1\n",
    "\n",
    "print('Extend transition model', len(tag_bigrams), 'by', new_bigrams)\n",
    "    \n",
    "model.bake()\n",
    "\n",
    "print('Edges', model.edge_count())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 5\n",
    "\n",
    "Finally, calculate accuracy of the model."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "training accuracy: 97.30%\n",
      "testing accuracy: 93.86%\n"
     ]
    }
   ],
   "source": [
    "training_acc = utils.accuracy(train_x, train_y, model, vocabulary=train_words)\n",
    "print(\"training accuracy: {:.2f}%\".format(100 * training_acc))\n",
    "\n",
    "testing_acc = utils.accuracy(test_x, test_y, model, vocabulary=train_words)\n",
    "print(\"testing accuracy: {:.2f}%\".format(100 * testing_acc))"
   ]
  }
 ],
 "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
}