Uncertainty/Naive_Bayes_classifier.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Naive Bayes Classifier for Spam Detection\n",
    "\n",
    "## Instructions\n",
    "\n",
    "Total Points: 10\n",
    "\n",
    "Complete this notebook and submit it. The notebook needs to be a complete project report with \n",
    "\n",
    "* your implementation,\n",
    "* documentation including a short discussion of how your implementation works and your design choices, and\n",
    "* experimental results (e.g., tables and charts with simulation results) with a short discussion of what they mean. \n",
    "\n",
    "Use the provided notebook cells and insert additional code and markdown cells as needed.\n",
    "\n",
    "## Introduction\n",
    "\n",
    "A spam detection agent gets as its percepts text messages and needs to decide if they are spam or not.\n",
    "Create a [naive Bayes classifier](https://en.wikipedia.org/wiki/Naive_Bayes_classifier) for the \n",
    "[UCI SMS Spam Collection Data Set](https://archive.ics.uci.edu/ml/datasets/SMS+Spam+Collection) to perform this task.\n",
    "\n",
    "__About the use of libraries:__ The point of this exercise is to learn how a Bayes classifier is built. You may use libraries for tokenizing, stop words and to create a document-term matrix, but you need to implement parameter estimation and prediction yourself.\n",
    "\n",
    "## Create a bag-of-words representation of the text messages [3 Points]\n",
    "\n",
    "The first step is to tokenize the text. Here is an example of how to load the data as a Pandas dataframe and then hoe to use the [natural language tool kit (nltk)](https://www.nltk.org/) to create tokens (separate terms) for the first message in the dataset."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>label</th>\n",
       "      <th>sms</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>ham</td>\n",
       "      <td>Go until jurong point, crazy.. Available only ...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>ham</td>\n",
       "      <td>Ok lar... Joking wif u oni...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>spam</td>\n",
       "      <td>Free entry in 2 a wkly comp to win FA Cup fina...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>ham</td>\n",
       "      <td>U dun say so early hor... U c already then say...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>ham</td>\n",
       "      <td>Nah I don't think he goes to usf, he lives aro...</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "  label                                                sms\n",
       "0   ham  Go until jurong point, crazy.. Available only ...\n",
       "1   ham                      Ok lar... Joking wif u oni...\n",
       "2  spam  Free entry in 2 a wkly comp to win FA Cup fina...\n",
       "3   ham  U dun say so early hor... U c already then say...\n",
       "4   ham  Nah I don't think he goes to usf, he lives aro..."
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import pandas as pd\n",
    "\n",
    "data = pd.read_csv(\"smsspamcollection/SMSSpamCollection\", sep='\\t',header = None,names = [\"label\",\"sms\"])\n",
    "data.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "message: Go until jurong point, crazy.. Available only in bugis n great world la e buffet... Cine there got amore wat... (label: ham)\n",
      "tokens: ['Go', 'until', 'jurong', 'point', ',', 'crazy', '..', 'Available', 'only', 'in', 'bugis', 'n', 'great', 'world', 'la', 'e', 'buffet', '...', 'Cine', 'there', 'got', 'amore', 'wat', '...']\n"
     ]
    }
   ],
   "source": [
    "import nltk\n",
    "# You need to install nltk and then download the punctuation database for the tokenizer.\n",
    "# ! pip install nltk\n",
    "# nltk.download('punkt')\n",
    "\n",
    "message = data.at[0,'sms']\n",
    "label = data.at[0,'label']\n",
    "print(f\"message: {message} (label: {label})\")\n",
    "\n",
    "tokens = nltk.word_tokenize(message)\n",
    "print(f\"tokens: {tokens}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Experiment with removing frequent words (called [stopwords](https://en.wikipedia.org/wiki/Stop_word)) and very infrequent words so you end up with a reasonable number of words used in the classifier. Maybe you need to remove digits or all non-letter characters. You may also use a stemming algorithm. \n",
    "\n",
    "Convert the tokenized data into a data structure that indicates for each for document what words it contains. The data structure can be a [document-term matrix](https://en.wikipedia.org/wiki/Document-term_matrix) with 0s and 1s, a pandas dataframe or some sparse matrix structure. Note: words, tokens and terms are often used interchangably. Make sure the data structure can be used to split the data into training and test documents (see below). A very convenient way to create document-term matrices is implemented in sklearn as a the \n",
    "text feature extractor [CountVectorizer](https://scikit-learn.org/stable/modules/generated/sklearn.feature_extraction.text.CountVectorizer.html)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Description and code goes here!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Report the 20 most frequent and the 20 least frequent words and there frequency in your data set. Remember: words are only counted once per document."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Code that prints the tables with the words"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Prepare training/testing data [0 Points]\n",
    "\n",
    "Split the data randomly into 80% for training and 20% for testing ([Example](https://github.com/mhahsler/CS7320-AI/blob/master/ML/ML_example.ipynb)). You can do the split directly on your document-term data structure."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Code goes here!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Learn parameters [3 Points]\n",
    "\n",
    "Use the training set to learn the parameters of the naive Bayes classifier.\n",
    "Remember, the naive Bayes classifier assumes conditional independence between words and estimates posteriori probabilities as:\n",
    "\n",
    "$$\\hat{P}(spam|message) \\propto score_{spam}(message) = P(spam) \\prod_{i=1}^n P(w_i | spam)$$\n",
    "$$\\hat{P}(ham|message) \\propto score_{ham}(message) = P(ham) \\prod_{i=1}^n P(w_i | ham)$$\n",
    "\n",
    "Note that $w_i$ is an indicator that is true (term is in the message) or false (term is not in the message) and each of these have a likelihood. That means you need not only consider likelihoods that \n",
    "a term appears in ham/spam messages, but also likelihoods that it does not appear in ham/spam messages.\n",
    "Trivially, $P(w_i = true | spam) = 1 - P(w_i = false | spam)$ (same for ham).\n",
    "\n",
    "Messages are classified as spam if the posteriori probability for spam is larger than for ham which is\n",
    "equivalent to \n",
    "$$score_{spam}(message) > score_{ham}(message)$$ \n",
    "\n",
    "You can also convert the scores back to probabilities using the normalization trick:\n",
    "$\\hat{P}(spam|message) = \\frac{1}{score_{spam}(message) + score_{ham}(message)} score_{spam}(message)$\n",
    "\n",
    "\n",
    "You therefore need to\n",
    "estimate \n",
    "\n",
    "* the priors $P(spam)$ and $P(ham)$ for messages, and \n",
    "* the likelihoods $P(w_i | spam)$ and $P(w_i | ham)$ for all the words/tokens you chose to use\n",
    "\n",
    "from counts obtained from the training data. Use [Laplacian smoothing](https://en.wikipedia.org/wiki/Additive_smoothing) for the estimation of\n",
    "likelihoods to avoid likelihoods of zero.\n",
    "\n",
    "Implementation note: Multiplying small number can be problematic. Most implementation add log likelihoods instead of multiplying likelihoods. Adding also means that you can use very efficient matrix algebra to calculate the score. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Description and code goes here!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Report the prior probabilities."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Code to print the prior probabilities"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Report the top 20 words for ham and for spam. The most important words can be found by looking at the ratio of likelihoods\n",
    "$\\frac{\\hat{P}(ham|message)}{\\hat{P}(spam|message)} = \\frac{score_{ham}(message)}{score_{spam}(message)}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Code that prints the tables with the words"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Evaluate the classification performance [4 Points] \n",
    "\n",
    "Classify the remaining 20% of the data (test set) and calculate classification accuracy. Accuracy is defined as the proportion of correctly classified test documents (see https://github.com/mhahsler/CS7320-AI/blob/master/ML/ML_example.ipynb).\n",
    "\n",
    "1. How good is your classifier's accuracy compared to the weak baseline classifier that always predicts the majority class and a strong baseline given by the [Naive Bayes classifier implemented in sklearn](https://scikit-learn.org/stable/modules/generated/sklearn.naive_bayes.MultinomialNB.html#sklearn.naive_bayes.BernoulliNB) \n",
    "(use a Bernoulli naive Bayes classifier for binary features). You are implementing the same classifier, so you should get the same performance.\n",
    "\n",
    "2. Inspect a few misclassified text messages and discuss why the classification failed.\n",
    "\n",
    "3. Discuss how you would deal with words in the test data that you have not seen in the training data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Description, code and discussion goes here!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bonus task [+1 Point]\n",
    "\n",
    "Describe how you could improve the classifier. Implement and test one of the improvements."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Code goes here!"
   ]
  }
 ],
 "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.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}