$\def\*#1{\mathbf{#1}}$
$\DeclareMathOperator*{\argmax}{arg\,max}$

# Mathematical Models : the case of the Naive Bayes classifier


```python
from scipy import stats
import matplotlib.pyplot as plt
import numpy as np
from math import log
%matplotlib inline
```

## Classifier

A classifier is a function $M$ that predicts the class label $\hat{y} \in \{c_1, c_2, \ldots, c_k\}$ for a given point $\*x \in \mathbb{R}^d$ :

$$\hat{y} = M(\*x)$$

## Supervised Learning

1. Collect a **Training Data Set** composed of points along with their known classes
2. Train Classifier
3. Make Predictions

### Collect Training Data

A training set of points with their known classes :

| Day | Outlook | Temp | Humidity | Beach? |
|-----|---------|------|----------|--------|
| 1   | Sunny   | High | High     | Yes    |
| 2   | Sunny   | High | Normal   | Yes    |
| 3   | Sunny   | Low  | Normal   | No     |
| 4   | Sunny   | Mild | High     | Yes    |
| 5   | Rain    | Mild | Normal   | No     |
| 6   | Rain    | High | High     | No     |
| 7   | Rain    | Low  | Normal   | No     |
| 8   | Cloudy  | High | High     | No     |
| 9   | Cloudy  | High | Normal   | Yes    |
| 10  | Cloudy  | Mild | Normal   | No     |

## Probabilistic Classification

We consider a dataset $D = \{\*x_1, \ldots, \*x_n\}$, with $y_i \in \{c_1, c_2, \ldots, c_k\}$ for all $i = 1, 2, \ldots, n$.

The **predicted class** for a new data point $\*x$ is obtained as follows :

$$
\hat{y} = \argmax_{c_i}\{P(c_i | \*x)\}
$$

### Bayes' Theorem

$$
P(A|B) = \frac{P(B|A)P(A)}{P(B)}
$$

This allows to reduce question such as P(outcome|data) to P(data|outcome).

### Bayes Classifier

Based on this formula, The **predicted class** for a new data point $\*x$ is obtained as follows :
$$
\begin{align}
\hat{y} &= \argmax_{c_i}\{P(c_i | \*x)\}\\
        &= \argmax_{c_i}\Bigg\{\frac{P(\*x | c_i) P(c_i)}{P(\*x)}\Bigg\}\\
        &= \argmax_{c_i}\{P(\*x | c_i) P(c_i)\}
\end{align}
$$

**Prior Probability Estimator** :

$$
\hat{P}(c_i) = \frac{|\*D_i|}{|\*D|} = \frac{n_i}{n}
$$

where $\*D_i = \{\*x_j \in \*D : y_j = c_i\}$, $|\*D| = n$, and $|\*D_i| = n_i$.

### Naive Bayes Classifier
In this case we assume that attributes are independent. This allows to write the likelyhood as follows :
    
$$
P(\*x|c_i) = P(x_1, x_2, \ldots, x_n | c_i) = \prod_{j = 1}^d P(x_i|c_i)
$$

For **categorical attributes**, 

$$
P(\*x|c_i) = \prod_{j = 1}^d P(x_i|c_i) \approx \prod_{j = 1}^d \hat{f}(\*v_j | c_i) = \prod_{j = 1}^d \frac{n_i(\*v_j)}{n_i}
$$

where $n_i(\*v_j)$ is the observed frequency of the value $\*v_j$ for the attribute $X_i$ in the class $c_i$.

| Day | Outlook | Temp | Humidity | Beach? |
|-----|---------|------|----------|--------|
| 1   | Sunny   | High | High     | Yes    |
| 2   | Sunny   | High | Normal   | Yes    |
| 3   | Sunny   | Low  | Normal   | No     |
| 4   | Sunny   | Mild | High     | Yes    |
| 5   | Rain    | Mild | Normal   | No     |
| 6   | Rain    | High | High     | No     |
| 7   | Rain    | Low  | Normal   | No     |
| 8   | Cloudy  | High | High     | No     |
| 9   | Cloudy  | High | Normal   | Yes    |
| 10  | Cloudy  | Mild | Normal   | No     |

| Outlook      | Beach | No Beach |
|--------------|-------|----------|
| Sunny        | 3/4   | 1/6      |
| Rain         | 0/4   | 3/6      |
| Cloudy       | 1/4   | 2/6      |

| Temperature  | Beach | No Beach |
|--------------|-------|----------|
| High         | 3/4   | 2/6      |
| Mild         | 1/4   | 2/6      |
| Low          | 0/4   | 2/6      |

| Humidity     | Beach | No Beach |
|--------------|-------|----------|
| High         | 2/4   | 2/6      |
| Normal       | 2/4   | 4/6      |

For example, based on the wather condition (Sunny, Mild, High), would this be a day to go to the beach ?

## Dealing with Zero counts

What happens when we consider (Sunny, Mild, Low), where the value of Low Humidity dow not appear in the training set ?

* P(Beach|(Sunny, Mild, Low)) = 0
* P(No Beach|(Sunny, Mild, Low)) = 0

Add-one **discounting** is a traditional statistical technique to address this problem : add one to the frequency of all outcomes. By applying this rules, the probabilities become what follows.

| Outlook      | Beach | No Beach |
|--------------|-------|----------|
| Sunny        | 4/7   | 2/9      |
| Rain         | 1/7   | 4/9      |
| Cloudy       | 2/7   | 3/9      |

| Temperature  | Beach | No Beach |
|--------------|-------|----------|
| High         | 4/7   | 3/9      |
| Mild         | 2/7   | 3/9      |
| Low          | 1/7   | 3/9      |

| Humidity     | Beach | No Beach |
|--------------|-------|----------|
| High         | 3/7   | 3/9      |
| Normal       | 3/7   | 5/9      |
| Low          | 1/7   | 1/9      |

## Multivariate bernoulli models


```python
# Sunny, Rain, Cloudy, Low, Mild, High, Normal, High
data = np.array([
    [1, 0, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 1, 1, 0],
    [1, 0, 0, 1, 0, 0, 1, 0],
    [1, 0, 0, 0, 1, 0, 0, 1],
    [0, 1, 0, 0, 1, 0, 1, 0],
    [0, 1, 0, 0, 0, 1, 0, 1],
    [0, 1, 0, 1, 0, 0, 1, 0],
    [0, 0, 1, 0, 0, 1, 0, 1],
    [0, 0, 1, 0, 0, 1, 1, 0],
    [0, 0, 1, 0, 1, 0, 1, 0]])

target = np.array([1, 1, 0, 1, 0, 0, 0, 0, 1, 0])

from sklearn.naive_bayes import BernoulliNB
bnb = BernoulliNB()
bnb.fit(data, target)
bnb.predict_proba([[1, 0, 0, 0, 1, 0, 0, 1]])
```

This model assume independence between some variables which is obviously wrong. Why ?

## Multinomial models


```python
from sklearn.naive_bayes import MultinomialNB
mnb = MultinomialNB(alpha=1.0e-10)
mnb.fit(data, target)
mnb.predict_proba([[1, 0, 0, 0, 1, 0, 0, 1]])
```

## Numerical Attributes

For *numerical attributes*, we can, for example, assume a normal distribution for each clas $c_i$ :

$$
P(x_j | c_i) \propto f(x_j) = \frac{1}{\sqrt{2\sigma_{ij}^2\pi} } \; e^{ -\frac{(x_-\mu_{ij})^2}{2\sigma_{ij}^2} }
$$

where $\mu_{ij}$ and $\sigma_{ij}^2$ denote the mean and variance for attribute $X_j$ and class $c_i$.


```python
from sklearn import datasets

iris = datasets.load_iris()

from sklearn.naive_bayes import GaussianNB

gnb = GaussianNB()

y_pred = gnb.fit(iris.data, iris.target).predict(iris.data)

print("Number of mislabeled points out of a total {} points : {}".format(iris.data.shape[0],
                                                                         (iris.target != y_pred).sum()))                  
```

## Classifier Evaluation

### Performance Measure

* $\*D$ : the data set composed of $n$ points in a $d$ dimensional space
* $k$ : the number of classes
* $M$ : the classifier
* $y_i$ : the "true" class that corresponds to $\*x_i \in \*D$
* $\hat{y}_i = M(\*x_i)$ : the predicted class
    
#### Error Rate

The fraction of incorrect predictions :

$$
Error\ Rate = \frac{1}{n} \sum_{i = 1}^n I(y_i \neq \hat{y}_i)
$$

#### Accuracy

The fraction of correct predictions :
$$
Accuracy = \frac{1}{n} \sum_{i = 1}^n I(y_i = \hat{y}_i) = 1 - Error\ Rate
$$

### Evaluation

The data set $\*D$ is split into two disjoint sets :

* **Training set** : used to train $M$
* **Testing set** : used to evaluate the performance measure (denoted $\theta$) of $M$

#### $K$-fold Cross-Validation

The data set $\*D$ is divided into $K$ equal-sized parts, denoted $\*D_1, \*D_2, \ldots, \*D_K$, called folds.

For each $i = 1,2,\ldots,K$, a model $M_i$ is trained and the corresponding measure $\theta_i$ is evaluated with respect to :

* $\*D_i$ : the testing set
* $\*D \backslash \*D_i = \cup_{j \neq i} \*D_j$ : the training set

This lead estimate the expected and variance values of the performance measure as follows,

* $\displaystyle \hat{\mu}_{\theta} = E[\theta] = \frac{1}{K} \sum_{i=1}^K \theta_i$
* $\displaystyle \hat{\sigma}_{\theta}^2 = \frac{1}{K} \sum_{i=1}^K (\theta_i - \hat{\mu}_{\theta})^2$

When $K = 1$ this validation method is called the **leave-one-out** cross-validation method.

## References :

* **The Data Science Design Manual**, by Steven Skiena, 2017, Springer;
* Python notebooks available at [http://data-manual.com/data](http://data-manual.com/data);
* Lectures slides available at [http://www3.cs.stonybrook.edu/~skiena/data-manual/lectures/](http://www3.cs.stonybrook.edu/~skiena/data-manual/lectures/).
* The Google Developers channel : Machine Learning Recipes
* Spring 2015 Boston University CS591 "Tools and Techniques for Data Mining and Applications" course 

6ccf29d4462d412afdbd7767085d64e3da563897
ipynb
Jupyter Notebook
lectures/Naive-Bayes.ipynb
juroland/datascience
557808f36f2b1362e8a53af70e2ca85ac40c0368
MIT
2017-09-18T07:26:17.000Z
2019-04-07T12:18:41.000Z
lectures/Naive-Bayes.ipynb
juroland/datascience
557808f36f2b1362e8a53af70e2ca85ac40c0368
MIT
2017-06-21T18:01:05.000Z
2017-09-04T14:41:33.000Z
lectures/Naive-Bayes.ipynb
juroland/datascience
557808f36f2b1362e8a53af70e2ca85ac40c0368
MIT
2017-10-03T09:03:12.000Z
2018-05-08T06:36:43.000Z
Qwen/Qwen-72B
1. YES
2. YES