naive_bayes.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import itertools\n",
    "from nltk.tokenize import RegexpTokenizer\n",
    "from nltk.corpus import stopwords\n",
    "from tqdm import tqdm\n",
    "from collections import Counter\n",
    "from functools import reduce\n",
    "from sklearn.metrics import accuracy_score, f1_score\n",
    "stopwords = stopwords.words('english')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "--2022-01-13 17:57:45--  https://archive.ics.uci.edu/ml/machine-learning-databases/00228/smsspamcollection.zip\n",
      "Resolving archive.ics.uci.edu (archive.ics.uci.edu)... 128.195.10.252\n",
      "Connecting to archive.ics.uci.edu (archive.ics.uci.edu)|128.195.10.252|:443... connected.\n",
      "HTTP request sent, awaiting response... 200 OK\n",
      "Length: 203415 (199K) [application/x-httpd-php]\n",
      "Saving to: ‘smsspamcollection.zip’\n",
      "\n",
      "smsspamcollection.z 100%[===================>] 198.65K   253KB/s    in 0.8s    \n",
      "\n",
      "2022-01-13 17:57:47 (253 KB/s) - ‘smsspamcollection.zip’ saved [203415/203415]\n",
      "\n",
      "Archive:  smsspamcollection.zip\n",
      "  inflating: SMSSpamCollection       \n",
      "  inflating: readme                  \n"
     ]
    }
   ],
   "source": [
    "!wget https://archive.ics.uci.edu/ml/machine-learning-databases/00228/smsspamcollection.zip\n",
    "!unzip smsspamcollection.zip "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Spam Classifier using Naive Bayes Algorithm\n",
    "\n",
    "In this notebook, we will train our model on Naive Bayes algorithm from scratch. \n",
    "\n",
    "$$\n",
    "P(C \\mid D)=\\frac{P(D \\mid C) P(C)}{P(D)}\n",
    "$$\n",
    "where $C$ stands for class (spam/non-spam) and $D$ stands for document.\n",
    "\n",
    "1. $P(C)$ stands for prior probabilities\n",
    "2. $P(D|C)$ stands for likelihoods\n",
    "3. Since $P(D)$ is constant for different classes:\n",
    "\n",
    "$$\n",
    "P(C \\mid D)\\propto P(D \\mid C) P(C)\n",
    "$$\n",
    "\n",
    "- As far as the proportional constant is concerned, we normalize probabilities such that they sum to 1. \n",
    "- We then compare these probabilities to assign labels. \n",
    "- Also, modelling $P(D)$ is difficult."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Important Points:\n",
    "1. So as we learn the joint distribution $P(C,D)$, and not exactly the posterior distribution $P(C|D)$, this is a generative model. \n",
    "2. Naive Bayes assumes that the features/words are independent of each other given class i.e. features are **conditionally independent** of each other. \n",
    "3. This means that the order of words in sentence doesn't matter. It considers a sentence as **bag of words** and doesn't account for context.\n",
    "4. However, it is known to work well in general which is why it's quite popular. It can have high bias due to the above reason, but then also has low variance."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Naive Bayes Algorithm\n",
    "\n",
    "The steps are as follows:\n",
    "1. Preprocess the data\n",
    "2. Split data (stratified if needed) into training and validation sets\n",
    "3. On Training data:\n",
    "    1. Calculate prior probabilities \n",
    "    2. Calculate likelihoods\n",
    "        1. Use Laplace Smoothing to avoid zero probabilities\n",
    "4. Evaluate on validation data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def preprocess(sentence, tokenizer):\n",
    "    words = tokenizer.tokenize(sentence)\n",
    "    words = [word.lower() for word in words if word.isalnum() and word not in stopwords]\n",
    "    sent = ' '.join(words)\n",
    "    return sent\n",
    "\n",
    "def get_corpus(path, tokenizer):\n",
    "    with open(path) as f:\n",
    "        data = f.read().splitlines()\n",
    "    data = list(map(lambda x: x.split('\\t'), data))\n",
    "    data = np.array(data)    \n",
    "    sents = np.array(list(map(lambda sent: preprocess(sent, tokenizer), data[:, 1])))\n",
    "    corpus = np.dstack((data[:,0],sents)).squeeze()\n",
    "    return corpus, sents"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# splitting data into train and validation sets\n",
    "def get_splits(corpus, val_pct):\n",
    "    val_size = int(val_pct * len(corpus))\n",
    "    idx = np.arange(len(corpus))\n",
    "    np.random.shuffle(idx)\n",
    "\n",
    "    val_idx = idx[-val_size:]\n",
    "    train_idx = idx[:-val_size]\n",
    "    train_corpus = corpus[train_idx]\n",
    "    val_corpus = corpus[val_idx]\n",
    "    return train_corpus, val_corpus\n",
    "\n",
    "# stratified splitting data \n",
    "def get_stratified_splits(corpus, val_pct):\n",
    "    corpus1 = corpus[corpus[:,0]=='ham']\n",
    "    corpus2 = corpus[corpus[:,0]=='spam']\n",
    "    assert len(corpus) == len(corpus1) + len(corpus2)\n",
    "\n",
    "    train_corpus1, val_corpus1 = get_splits(corpus1, val_pct)\n",
    "    train_corpus2, val_corpus2 = get_splits(corpus2, val_pct)\n",
    "    train_corpus = np.vstack((train_corpus1, train_corpus2))\n",
    "    val_corpus = np.vstack((val_corpus1, val_corpus2))\n",
    "    return train_corpus, val_corpus    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of Training examples: 4460\n",
      "Number of Validation examples: 1114 \n",
      "\n",
      "Checking class imablance..\n",
      "Percentage of non-spam messages: 0.87 \n",
      "\n",
      "Vocabulary size: 8729\n"
     ]
    }
   ],
   "source": [
    "tokenizer = RegexpTokenizer(r'\\w+')    \n",
    "val_pct = 0.2\n",
    "path = 'SMSSpamCollection'\n",
    "corpus, sents = get_corpus(path, tokenizer)\n",
    "train_corpus, val_corpus = get_stratified_splits(corpus, val_pct)\n",
    "\n",
    "print('Number of Training examples:', len(train_corpus))\n",
    "print('Number of Validation examples:', len(val_corpus),'\\n')\n",
    "print('Checking class imablance..')\n",
    "print('Percentage of non-spam messages:', np.mean(corpus[:,0]=='ham').round(2),'\\n')\n",
    "\n",
    "words = list(map(lambda sent: sent.split(' '), sents))\n",
    "vocab = list(set(itertools.chain(*words)))\n",
    "print('Vocabulary size:', len(vocab))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# get likelihoods\n",
    "def get_cond_prob(corpus):\n",
    "    words = list(map(lambda x: x.split(' '), corpus[:,1]))\n",
    "    freq_dict = dict(Counter(list(itertools.chain(*words))))\n",
    "    extra_tokens = set(vocab) - set(freq_dict.keys())\n",
    "    extra_freq_dict = dict(zip(extra_tokens, [0] * len(extra_tokens)))\n",
    "    freq_dict.update(extra_freq_dict)\n",
    "\n",
    "    # laplace smoothing \n",
    "    # adding 1 for solving issues of zero probabilities\n",
    "    cond_prob = {k:(v+1) / (sum(freq_dict.values()) + len(freq_dict)) for k,v in freq_dict.items()}\n",
    "    return cond_prob\n",
    "\n",
    "# get posterior probabilities\n",
    "def get_probs(words):\n",
    "    probs = []\n",
    "    for label in labels:\n",
    "        prior = class_priors[label]\n",
    "        cond_probs = list(map(lambda x: likelihoods[label][x], words))\n",
    "        likelihood = reduce(lambda x,y: x*y, cond_probs)\n",
    "        prob = prior * likelihood\n",
    "        probs.append(prob)\n",
    "    \n",
    "    # normalizing probabilities\n",
    "    probs = probs / np.sum(probs)\n",
    "    return probs    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# get prior probabilities\n",
    "labels = list(set(corpus[:,0]))\n",
    "class_priors = {}\n",
    "for label in labels:\n",
    "    class_priors[label] = sum(train_corpus[:,0]==label) / len(train_corpus)\n",
    "\n",
    "# get likelihoods\n",
    "likelihoods = {}\n",
    "for label in labels:\n",
    "    label_train_corpus = train_corpus[train_corpus[:,0]==label]\n",
    "    likelihoods[label] = get_cond_prob(corpus)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0.87, 0.93)"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def get_predictions(val_corpus):\n",
    "    sents = list(map(lambda x: x.split(' '), val_corpus[:,1]))\n",
    "    y_pred = []\n",
    "    for words in sents:\n",
    "        probs = get_probs(words)\n",
    "        label_idx = probs.tolist().index(max(probs))\n",
    "        pred = labels[label_idx]\n",
    "        y_pred.append(pred)\n",
    "    y_pred = np.array(y_pred)\n",
    "    return y_pred\n",
    "\n",
    "# predictions\n",
    "y_pred = get_predictions(val_corpus).tolist()\n",
    "\n",
    "# ground truth\n",
    "y_val = val_corpus[:,0].tolist()  \n",
    "assert len(y_val) == len(y_pred)    \n",
    "\n",
    "# metrics\n",
    "accuracy_score(y_val, y_pred).round(2), f1_score(y_val, y_pred, pos_label='ham').round(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "951daa5e1959839fcb325fff331f52e72634f7a1be998f6081ed7f433b63f1b3"
  },
  "kernelspec": {
   "display_name": "Python 3.8.11 64-bit ('base': conda)",
   "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.8.11"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}