notebooks/naive-bayes-classifier.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Naive Bayes Classifier\n",
    "\n",
    "---\n",
    "\n",
    "In this tutorial, we will introduce the **naive Bayes classifier**, which is a simple yet effective classification method based on probability and reasoning under uncertainty."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bayes Rule <a name=\"bayes-rule\"></a>\n",
    "\n",
    "---\n",
    "\n",
    "First, we introduce the Bayes rule, which the naive Bayes classifier is based on.\n",
    "\n",
    "From the <a href=\"https://en.wikipedia.org/wiki/Chain_rule_(probability)\">product/chain rule</a>, we know that given two propositions $A$ and $B$, we have \n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "P(A,B) & = P(B) * P(A\\ |\\ B) \\\\\n",
    "& = P(A) * P(B\\ |\\ A).\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "We can easily convert the above equation into the following one by dividing all parts by $P(B)$:\n",
    "\n",
    "$$\n",
    "P(A\\ |\\ B) = \\frac{P(A) * P(B\\ |\\ A)}{P(B)}.\n",
    "$$\n",
    "\n",
    "The above equation is exactly the **Bayes rule**. It is named after the famous statistician [Thomas Bayes](https://en.wikipedia.org/wiki/Thomas_Bayes), who proposed this rule/theorem.\n",
    "\n",
    "We can also extend the Bayes rule to more variables. Given propositions $X_1, X_2, \\dots, X_n, Y$, we have \n",
    "\n",
    "$$\n",
    "P(Y\\ |\\ X_1, X_2, \\dots, X_n) = \\frac{P(Y) * P(X_1, X_2, \\dots, X_n\\ |\\ Y)}{P(X_1, X_2, \\dots, X_n)}.\n",
    "$$\n",
    "\n",
    "<!-- <img src='img/thomas-bayes.gif' width=200></img> -->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Why is Bayes rule useful?\n",
    "\n",
    "The Bayes rule looks very simple, and is just one step of conversion from the product rule. However, it is very helpful for reasoning under uncertainty due to the following interpretation.\n",
    "\n",
    "- Let $A$ be the proposition that we want to reason. We call it the **query proposition**, and its probability $P(A)$ is called the **prior probability/belief**.\n",
    "- Let $B$ be another proposition that we can observe as evidence. We call it the **evidence proposition**, and its probability $P(B)$ indicates the probability that we observe the evidence.\n",
    "- $P(A\\ |\\ B)$ is the probability of the query $A$ given that the evidence $B$ has been observed. This is called the **posterior probability/belief** given the evidene $B$.\n",
    "- $P(B\\ |\\ A)$ is the conditional probability of the evidence $B$ given that $A$ is true.\n",
    "\n",
    "In most cases, it is easier to estimate or calculate $P(A)$, $P(B)$ and $P(B\\ |\\ A)$ than directly estimating $P(A\\ |\\ B)$. Thus, by the Bayes rule, we can calculate the posterior probability $P(A\\ |\\ B)$ from our domain knowledge of $P(A)$, $P(B)$ and $P(B\\ |\\ A)$. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example: Medical Test\n",
    "\n",
    "You are worried about having a rare cancer. The cancer is very rare, occurring in only one of every 10,000 people. You go with the cancer test, which has 99% accuracy (if you have the cancer, it shows that you do with 99% probability; if you don't have the cancer, it shows that you do not with 99% probability).\n",
    "\n",
    "#### QUESTION: \n",
    "\n",
    "If your test result comes back positive, what are your chances that you actually have the cancer?\n",
    "\n",
    "#### ANSWER\n",
    "\n",
    "First we define the following propositions:\n",
    "\n",
    "- $A$: You have the cancer\n",
    "- $B$: Your test result comes back positive.\n",
    "\n",
    "From the problem description, we know that the probability to have the cancer is 1/10000, i.e.,\n",
    "\n",
    "$$\n",
    "P(A) = \\frac{1}{10000} = 0.0001,\n",
    "$$\n",
    "\n",
    "In addition, from the 99% accuracy of the test, we have\n",
    "\n",
    "$$\n",
    "P(B\\ |\\ A) = 0.99,\n",
    "$$\n",
    "\n",
    "$$\n",
    "P(\\neg B\\ |\\ \\neg A) = 0.99.\n",
    "$$\n",
    "\n",
    "The question is to calculate $P(A\\ |\\ B)$. By Bayes rule, we have\n",
    "\n",
    "$$\n",
    "P(A\\ |\\ B) = \\frac{P(A) * P(B\\ |\\ A)}{P(B)},\n",
    "$$\n",
    "\n",
    "where $P(A) = 0.0001$ and $P(B\\ |\\ A) = 0.99$ are already known. However, $P(B)$ is not known yet. Here, we use the probability rules introduced in a previous [tutorial](https://github.com/meiyi1986/tutorials/blob/master/notebooks/reasoning-under-uncertainty-basics.ipynb) to calculate $P(B)$.\n",
    "\n",
    "First, we use the **sum rule** to include $A$ jointly with $B$ as follows:\n",
    "\n",
    "$$\n",
    "P(B) = P(B, A) + P(B, \\neg A).\n",
    "$$\n",
    "\n",
    "Then, for each term on the right hand side, we use the **product rule** as follows.\n",
    "\n",
    "$$\n",
    "P(B, A) = P(A) * P(B\\ |\\ A),\n",
    "$$\n",
    "\n",
    "$$\n",
    "P(B, \\neg A) = P(\\neg A) * P(B\\ |\\ \\neg A).\n",
    "$$\n",
    "\n",
    "The first equation can be easily calculated as \n",
    "$$\n",
    "\\begin{aligned}\n",
    "P(B, A) & = P(A) * P(B\\ |\\ A) \\\\\n",
    "& = 0.0001 \\times 0.99 = 0.000099.\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "To calculate the second equation, we use the **normalisation rule** as follows.\n",
    "\n",
    "$$\n",
    "P(\\neg A) = 1 - P(A) = 0.9999,\n",
    "$$\n",
    "\n",
    "$$\n",
    "P(B\\ |\\ \\neg A) = 1 - P(\\neg B\\ |\\ \\neg A) = 0.01.\n",
    "$$\n",
    "\n",
    "Thus, we have \n",
    "\n",
    "$$\n",
    "P(B, \\neg A) = 0.9999 \\times 0.01 = 0.009999.\n",
    "$$\n",
    "\n",
    "Overall, we have $P(B) = P(B, A) + P(B, \\neg A) = 0.000099 + 0.009999 = 0.010098$.\n",
    "\n",
    "Finally, we can have \n",
    "\n",
    "$$\n",
    "P(A\\ |\\ B) = \\frac{P(A) * P(B\\ |\\ A)}{P(B)} = \\frac{0.0001 \\times 0.99}{0.010098} \\approx 0.01.\n",
    "$$\n",
    "\n",
    "We can see that even with the positive test result, the chance of actually having the cancer is still only 1%. This is due to the very small prior probability $P(A) = 0.0001$. Note that the positive test result already makes the posterior probability 100 times as the prior probability."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Naive Bayes Classifier Algorithm <a name=\"nb\"></a>\n",
    "\n",
    "---\n",
    "\n",
    "### Classification by Probability <a name=\"prob\"></a>\n",
    "\n",
    "In classification, an instance is represented as a feature vector. If we consider the classification problem from the perspective of probability, we are asking the following question:\n",
    "\n",
    "> **QUESTION**: What is the **conditional probability** of the **class label** of an instance given its **feature vector**?\n",
    "\n",
    "For this purpose, we define the class label and each feature as a random variable. Let $Y$ be the random variable for the class label, and $X_i$ the random variable of the $i$th feature, given an instance (feature vector) $[X_1 = x_1, \\dots, X_n = x_n]$, we aim to estimate\n",
    "\n",
    "$$\n",
    "P(Y = y\\ |\\ X_1 = x_1, \\dots, X_n = x_n)\n",
    "$$\n",
    "\n",
    "for each class label $y$. Then, we can use the **winner-take-all** approach, and predict the class label with the highest probability."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Use Bayes Rule <a name=\"nb-rule\"></a>\n",
    "\n",
    "To directly estimate the $P(Y = y\\ |\\ X_1 = x_1, \\dots, X_n = x_n)$ from the training data, we need to\n",
    "\n",
    "1. Find the instances with $[X_1 = x_1, \\dots, X_n = x_n]$ in the training data. Say that we have found $M$ such instances from the training data.\n",
    "2. Find the instances with class label $Y = y$ among those in Step 1. Say we have found $K (K \\leq M)$ such instances.\n",
    "3. Calculate the empirical probability $P(Y = y\\ |\\ X_1 = x_1, \\dots, X_n = x_n) = \\frac{K}{M}$.\n",
    "\n",
    "Normally, this direction estimation requires a **LOT** of training instances to ensure a reasonable accuracy of the empirical probability for any possible test instance (feature vector). For example, if there are 10 binary features and 2 classes, the number of different feature vectors is $2^{10} = 1024$. If we need at least 30 instances for each possible feature vector and each class to ensure the accuracy of the empirical probability, then we need as least $30 \\times 1024 \\times 2 = 61440$ instances in total.\n",
    "\n",
    "To address this issue, the naive Bayes classifier uses the Bayes rule as follows:\n",
    "\n",
    "$$\n",
    "P(Y = y\\ |\\ X_1 = x_1, \\dots, X_n = x_n) = \\frac{P(Y = y) * P(X_1 = x_1, \\dots, X_n = x_n\\ |\\ Y = y)}{P(X_1 = x_1, \\dots, X_n = x_n)}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Conditional Independence Assumption <a name=\"independence\"></a>\n",
    "\n",
    "Note that the use of Bayes rule still does not relax the requirement, since we need the same number of instances to estimate $P(X_1 = x_1, \\dots, X_n = x_n\\ |\\ Y)$ and $P(X_1 = x_1, \\dots, X_n = x_n)$. Therefore, the naive Bayes classifier further makes the following assumption:\n",
    "\n",
    "> **DEFINITION**: In the **conditional independence assumption**, the features are assumed to be conditionally independent with each other given the class label. \n",
    "\n",
    "For each $x_1 \\in \\Omega(X_1), \\dots, x_n \\in \\Omega(X_n), y \\in \\Omega(Y)$, we have\n",
    "\n",
    "$$\n",
    "P(X_1 = x_1, \\dots, X_n = x_n\\ |\\ Y = y) = P(X_1 = x_1\\ |\\ Y = y) * \\dots * P(X_n = x_n\\ |\\ Y = y).\n",
    "$$\n",
    "\n",
    "Therefore,\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "P(Y = y\\ |\\ X_1 = x_1, \\dots, X_n = x_n) & = \\frac{P(Y = y) * P(X_1 = x_1, \\dots, X_n = x_n\\ |\\ Y = y)}{P(X_1 = x_1, \\dots, X_n = x_n)} \\\\\n",
    "& = \\frac{P(Y = y) * P(X_1 = x_1\\ |\\ Y = y) * \\dots * P(X_n = x_n\\ |\\ Y = y)}{P(X_1 = x_1, \\dots, X_n = x_n)}\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "Thus, we only need to estimate $P(X_i = x_i\\ |\\ Y = y)$ for each feature independently. This can greatly reduce the amount of training data required, as there are much more instances matching $[X_i = x_i, Y = y]$ for each feature.\n",
    "\n",
    "> **NOTE**: The conditional independence assumption is **naive** (this is why the algorithm is called **naive** Bayes classifier). In practice, this assumption is almost always wrong. However, the naive Bayes classifier can often show high classification accuracy. Why?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### No Need for Denominator Calculation <a name=\"denom\"></a>\n",
    "\n",
    "Note that the demoninator $P(X_1 = x_1, \\dots, X_n = x_n)$ is independent of the class label. Therefore, it is a constant coefficient in the conditional probabilities of all the class labels. In other words, the conditional probabilities of the class labels are proportional to its enumerator. That is,\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "P(Y = y\\ |\\ X_1 = x_1, \\dots, X_n = x_n) & = \\alpha * P(Y = y) * P(X_1 = x_1\\ |\\ Y = y) * \\dots * P(X_n = x_n\\ |\\ Y = y) \\\\\n",
    "& \\propto P(Y = y) * P(X_1 = x_1\\ |\\ Y = y) * \\dots * P(X_n = x_n\\ |\\ Y = y)\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "where $\\alpha = 1/P(X_1 = x_1, \\dots, X_n = x_n)$ is the constant coefficient.\n",
    "\n",
    "Therefore, the class label with the highest $P(Y = y) * P(X_1 = x_1\\ |\\ Y = y) * \\dots * P(X_n = x_n\\ |\\ Y = y)$ will have the highest conditional probability."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Overall Algorithm <a name=\"overall\"></a>\n",
    "\n",
    "Putting everything together, the pseudo code of the overall naive Bayes classifier is as follows."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```Python\n",
    "'''\n",
    "Preprocessing, calculate P(class) and P(feature = value | class) for each class and feature\n",
    "'''\n",
    "for each class_label:\n",
    "    count the number of training instances N[class_label] matching this label\n",
    "    P[class_label] = N[class_label] / N\n",
    "    for each feature:\n",
    "        for each value in domain[feature]:\n",
    "            count the number of training instances N[feature, value, class_label] matching the feature value\n",
    "            P[feature, value, class_label] = N[feature, value, class_label] / N[class_label]\n",
    "\n",
    "'''\n",
    "Make prediction for a new feature_vector\n",
    "'''\n",
    "def predict(feature_vector):\n",
    "    pred_class = None\n",
    "    pred_prob = 0\n",
    "    for each class_label:\n",
    "        score[class_label] = P[class_label]\n",
    "        for each feature:\n",
    "            score[class_label] = score[class_label] * P[feature, feature_vector[feature], class_label]\n",
    "        \n",
    "        if score[class_label] > pred_prob:\n",
    "            pred_class = class_label\n",
    "            pred_prob = score[class_label]\n",
    "    \n",
    "    return (pred_class, pred_prob)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Case Study on Bank Loan Application <a name=\"case-study\"></a>\n",
    "\n",
    "---\n",
    "\n",
    "Assuming that we are to build a system to approve/decline bank loan applications. The system learns the decision based on three features:\n",
    "\n",
    "1. The **Job** feature: whether the applicant has a job or not?\n",
    "2. The **Deposit** feature: whether the applicant has a high or low deposit?\n",
    "3. The **Family** feature: whether the applicant is single, couple (without child), or with children?\n",
    "\n",
    "Below are 10 historical applications with their decisions. We will use them to train our Naive Bayes classifier.\n",
    "\n",
    "| Applicant | Job | Deposit | Family | Decision |\n",
    "| --------- | --- | ------- | ------ | -------- |\n",
    "|     1     | true | low    | single | Approve  |\n",
    "|     2     | true | low    | couple | Approve  |\n",
    "|     3     | true | high    | single | Approve  |\n",
    "|     4     | true | high    | single | Approve  |\n",
    "|     5     | false | high    | couple | Approve  |\n",
    "|     6     | true | low    | couple | Decline  |\n",
    "|     7     | false | low    | couple | Decline  |\n",
    "|     8     | true | low    | children | Decline  |\n",
    "|     9     | false | low    | single | Decline  |\n",
    "|    10     | false | high    | children | Decline  |\n",
    "\n",
    "To calculate the `P(class)` and `P(feature = value | class)` for each class and feature, we count the **number of instances** matching different class labels and feature values as follows.\n",
    "\n",
    "| Class | Approve | Decline |\n",
    "| ----- | ------- | ------- |\n",
    "| Total |    5    |    5    |\n",
    "| Job = true |    4    |    2    |\n",
    "| Job = false |    1    |    3    |\n",
    "| Dep = low |    2    |    4    |\n",
    "| Dep = high |    3    |    1    |\n",
    "| Fam = single |    3    |    1    |\n",
    "| Fam = couple |    2    |    2    |\n",
    "| Fam = children |    0    |    2    |\n",
    "\n",
    "Then, we calculate the (conditional) probabilities as follows.\n",
    "\n",
    "\n",
    "| Class | Approve | Decline |\n",
    "| ----- | ------- | ------- |\n",
    "| Total |    5/10    |    5/10    |\n",
    "| Job = true |    4/5    |    2/5    |\n",
    "| Job = false |    1/5    |    3/5    |\n",
    "| Dep = low |    2/5    |    4/5    |\n",
    "| Dep = high |    3/5    |    1/5    |\n",
    "| Fam = single |    3/5    |    1/5    |\n",
    "| Fam = couple |    2/5    |    2/5    |\n",
    "| Fam = children |    0/5    |    2/5    |\n",
    "\n",
    "Given a new instance [Job = true, Dep = high, Fam = children], we use the naive Bayes classifier to calculate the **class score** (ignoring the denominator) for each class label (Decline and Approve).\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& P(Decline\\ |\\ Job = true, Dep = high, Fam = children) \\\\\n",
    "& \\propto P(Decline) * P(Job = true\\ |\\ Decline) * P(Dep = high\\ |\\ Decline) * P(Fam = children\\ |\\ Decline) \\\\\n",
    "& = 5/10 \\times 2/5 \\times 1/5 \\times 2/5 \\\\\n",
    "& = 0.016.\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& P(Approve\\ |\\ Job = true, Dep = high, Fam = children) \\\\\n",
    "& \\propto P(Approve) * P(Job = true\\ |\\ Approve) * P(Dep = high\\ |\\ Approve) * P(Fam = children\\ |\\ Approve) \\\\\n",
    "& = 5/10 \\times 4/5 \\times 3/5 \\times 0/5 \\\\\n",
    "& = 0.\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "The predicted class will be **Decline**, since it has the highest score."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Dealing with Zero Occurrence <a name=\"zero\"></a>\n",
    "\n",
    "---\n",
    "\n",
    "In the above example, if we further look into the instance, we can see that the applicable is actually very promising. The applicant has a job and the deposit is high. However, the application is declined, because $P(Fam = children\\ |\\ Approve) = 0$ in the training data (also note that the two declined applications with $Fam = children$ had either no job or low deposit). This cancels out all the effects to other features, since zero multiplies everything is still zero.\n",
    "\n",
    "To deal with zero occurrence for a feature that voids the effects of all the other features, we can take a simple approach: we start counting the number of instances from 1 rather than 0.\n",
    "\n",
    "After adjusting the counting, the table of the number of instances matching the class labels and feature values is shown as follows.\n",
    "\n",
    "| Class | Approve | Decline |\n",
    "| ----- | ------- | ------- |\n",
    "| Total |    6    |    6    |\n",
    "| Job = true |    5    |    3    |\n",
    "| Job = false |    2    |    4    |\n",
    "| Dep = low |    3    |    5    |\n",
    "| Dep = high |    4    |    2    |\n",
    "| Fam = single |    4    |    2    |\n",
    "| Fam = couple |    3    |    3    |\n",
    "| Fam = children |    1    |    3    |\n",
    "\n",
    "We can see that compared with the original table, each entry in this adjusted table is incremented by 1.\n",
    "\n",
    "From this table, we calculate the (conditional) probabilities as follows.\n",
    "\n",
    "$$\n",
    "P(Class) = \\frac{N(Class)}{N(Class = Approve) + N(Class = Decline)}\n",
    "$$\n",
    "\n",
    "$$\n",
    "P(Job\\ |\\ Class) = \\frac{N(Job, Class)}{N(Job = true, Class) + N(Job = false, Class)}\n",
    "$$\n",
    "\n",
    "$$\n",
    "P(Dep\\ |\\ Class) = \\frac{N(Dep, Class)}{N(Dep = low, Class) + N(Dep = high, Class)}\n",
    "$$\n",
    "\n",
    "$$\n",
    "P(Fam\\ |\\ Class) = \\frac{N(Fam, Class)}{N(Fam = single, Class) + N(Fam = couple, Class) + N(Fam = children, Class)}\n",
    "$$\n",
    "\n",
    "Then, the table for the (conditional) probabilities is below.\n",
    "\n",
    "| Class | Approve | Decline |\n",
    "| ----- | ------- | ------- |\n",
    "| Total |    6/12    |    6/12    |\n",
    "| Job = true |    5/7    |    3/7    |\n",
    "| Job = false |    2/7    |    4/7    |\n",
    "| Dep = low |    3/7    |    5/7    |\n",
    "| Dep = high |    4/7    |    2/7    |\n",
    "| Fam = single |    4/8    |    2/8    |\n",
    "| Fam = couple |    3/8    |    3/8    |\n",
    "| Fam = children |    1/8    |    3/8    |\n",
    "\n",
    "From the new table, we calculate the class scores as follows.\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& P(Decline\\ |\\ Job = true, Dep = high, Fam = children) \\\\\n",
    "& \\propto P(Decline) * P(Job = true\\ |\\ Decline) * P(Dep = high\\ |\\ Decline) * P(Fam = children\\ |\\ Decline) \\\\\n",
    "& = 6/12 \\times 3/7 \\times 2/7 \\times 3/8 \\\\\n",
    "& = 0.0230.\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& P(Approve\\ |\\ Job = true, Dep = high, Fam = children) \\\\\n",
    "& \\propto P(Approve) * P(Job = true\\ |\\ Approve) * P(Dep = high\\ |\\ Approve) * P(Fam = children\\ |\\ Approve) \\\\\n",
    "& = 6/12 \\times 5/7 \\times 4/7 \\times 1/8 \\\\\n",
    "& = 0.0255.\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "The predicted class now becomes **Approve**. This shows the effectiveness of dealing with zero occurrence."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "- More tutorials can be found [here](https://github.com/meiyi1986/tutorials).\n",
    "- [Yi Mei's homepage](https://meiyi1986.github.io/)"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "authorship_tag": "ABX9TyOLYiX4MNVN+YKTRqYwBPrZ",
   "collapsed_sections": [],
   "name": "probability_product_rule.ipynb",
   "provenance": []
  },
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}