Naive Bayes

Suppose our training set consists of data samples $D=\{({\mathbf{x}}_1,y_1),....,({\mathbf{x}}_N,y_N)\},{\mathbf{x}}_{\mathbf{i}}\in {\mathbb{R}}^d$, where $D=\{({\mathbf{x}}_i,y_i)\}$ are realizations of a random sample that follows unknown joint distribution $P(\mathbf{X},Y)$.

Assumptions:

1. Features are conditionally independent (Naive bayes assumption): $$P(\mathbf{X}|Y)=\prod _{j=1}^{d}P(X_j|Y)$$

2. MLE assumption: Random sample is identically distributed.

3. Positional independence: The position of features does not matter (used in Multinomial case).

By applying bayes rule (applying on distribution $P(\cdot )$ to make things general), we have:

$$P(Y|\mathbf{X})=\frac{P(\mathbf{X},Y)}{P(\mathbf{X})}=\frac{P(\mathbf{X}|Y)P(Y)}{P(\mathbf{X})}$$

By substituting the assumption:

$$P(Y|\mathbf{X})=\frac{\prod _{j=1}^{d}P(X_j|Y)P(Y)}{P(\mathbf{X})}$$

Since the probability distribution $P(\mathbf{X})$ characterised by $F_{\mathbf{X}}(\mathbf{x})$ is constant for any given $\mathbf{x}$, we can drop it from the equation because it only changes $P(Y|\mathbf{X})$ by a proportion:

$$P(Y|\mathbf{X})\propto P(Y)\prod _{j=1}^{d}P(X_j|Y)$$

Our goal is to find a class $\hat{y}$ that maximize the probability given input $\mathbf{X}=\mathbf{x}$:

$$\begin{array}{r}\hat{y}=\underset{y}{\arg max}\sum _{j=1}^d\log P_{X_j|Y}(x_j|y)+\log P_Y(y)\end{array}$$

Bernoulli Naive Bayes

In order to solve for $\hat{y}$, we need to first find $\log P(X_i|Y)$ and $\log P(Y)$. Assume that our features are discrete and takes values $X_j\in \{0,1\}$ and we have $k$ classes, $Y\in \{0,...,k\}$. Then it is nature to also assume that the conditional distribution of one feature $X_j$ given $Y=y$ follows a bernoulli distribution with unknown parameters ${\mu }_{jy}$. That is, for $i$th input (${\mathbf{x}}_i,y_i$) the pmf of $j$th feature given $y_i$ can be written as:

$$p_{X_j|Y}(x_{ij}|y_i;{\mu }_{j{y}_i})={\mu }_{j{y}_i}^{x_{ij}}(1-{\mu }_{j{y}_i}{)}^{1-x_{ij}}$$

Besides parameter ${\mu }_{j{y}_i}$, we have parameter ${\pi }_{y_i}$ which is defined as the prior probability of class $y_i$ (This is valid because this is part of the joint distribution):

$${\pi }_{y_i}=P(Y=y_i)$$

Then, the likelihood function can be written as $\mathit{\theta }=<\mathit{\mu }\mathbf{,}\mathit{\pi }>$:

$$L(\mathit{\theta };D)=\prod _{i=1}^{N}P(\mathbf{X},Y;\mathit{\theta })=\prod _{i=1}^N{\pi }_{y_i}\prod _{j=1}^d{\mu }_{j{y}_i}^{x_{ij}}(1-{\mu }_{j{y}_i}{)}^{1-x_{ij}}$$

subject to constraint $\sum _{i=1}^K{\pi }_i=1$

Then the log likelihood function:

$$l(\mathit{\theta };D)=\sum _{i=1}^N[\log ({\pi }_{y_i})\sum _{j=1}^d{x}_{ij}\log ({\mu }_{j{y}_i})+(1-x_{ij})\log (1-{\mu }_{j{y}_i})]$$

subject to constraint $\sum _{i=1}^K{\pi }_i=1$

Taking partial derivative w.r.t ${\mu }_{jk}$:

$$\begin{array}{rl}\frac{\partial l(\mathit{\theta };D)}{\partial {\mu }_{jk}}& =0\\ ⟹\sum _{i=1}^{n}I[y_i=k](\frac{x_{ij}}{{\mu }_{jk}}-\frac{1-x_{ij}}{1-{\mu }_{jk}})& =0\\ ⟹\sum _{i=1}^{n}I[y_i=k]\frac{x_{ij}}{{\mu }_{jk}}& =\sum _{i=1}^{n}I[y_i=k]\frac{1-x_{ij}}{1-{\mu }_{jk}}\\ ⟹\sum _{i=1}^{n}I[y_i=k](1-{\mu }_{jk})x_{ij}& =\sum _{i=1}^{n}I[y_i=k](1-x_{ij}){\mu }_{jk}\\ ⟹{\hat{\mu }}_{jk}& =\frac{\sum _{i=1}^{N}I[x_{ij}=1\text{ and }{y}_i=k]}{\sum _{i=1}^{N}I[y_i=k]}\end{array}$$

Taking partial derivative w.r.t ${\pi }_k$ and constraint $\sum _{i=1}^K{\pi }_i=1$ (Lagrange multiplier):

$$\frac{\partial l(\mathit{\theta };D)}{\partial {\pi }_k}+\lambda \frac{\partial \sum _{i=1}^K{\pi }_i}{\partial {\pi }_k}=0$$

$$⟹\lambda =-\sum _{i=1}^N\frac{I[y_i=k]}{{\pi }_k}$$

$$⟹{\pi }_k=-\sum _{i=1}^N\frac{I[y_i=k]}{\lambda }$$

By substituting $\lambda$ with $\sum _{i=1}^N{\pi }_i=1⟹\lambda =-N$:

$${\hat{\pi }}_k=\sum _{i=1}^N\frac{I[y_i=k]}{N}$$

The result is same if we assume $Y$ follows Multinomial distribution with constraint on $p$ and $n=1$.

Multinomial Naive Bayes

In multinomial case, our features are counts $X_j\in \{0,.....,M\}$.

The derivation of Multinomial NB is similar to Bernoulli case, the only difference is that, in multinomial, we assume the conditional distribution of $\mathbf{X}$ given $Y=y$ follows a multinomial distribution. That is, the conditional pmf for $i$th input $({\mathbf{x}}_i|y_i)$ is defined as:

$$p_{\mathbf{X}|Y}({\mathbf{x}}_i|y_i)=\frac{M_i!}{x_{i1}!....x_{id}!}\prod _{j=1}^d{\mu }_{j{y}_i}^{x_{ij}}$$

Where, $M_i$ represents the total counts for sample $i$.

By positional independence:

$$p_{\mathbf{X}|Y}({\mathbf{x}}_i|y_i)=\prod _{j=1}^d{\mu }_{j{y}_i}^{x_{ij}}$$

Then, we can write the likelihood function as:

$$L(\mathit{\theta };D)=\prod _{i=1}^{N}P(\mathbf{X},Y;\mathit{\theta })=\prod _{i=1}^N{\pi }_{y_i}\prod _{j=1}^d{\mu }_{j{y}_i}^{x_{ij}}$$

subject to constraints:

$$\sum _{i=1}^K{\pi }_i=1$$

$$\sum _{j=1}^d{\mu }_{jk}=1$$

$$\sum _{j=1}^d{x}_{ij}=M_i$$

By solving the contrained maximization problem, we have the estimates:

$${\hat{\mu }}_{jk}=\frac{\sum _{i=1}^{N}I[y_i=k]x_{ij}+l}{\sum _{i=1}^{N}I[y_i=k]\sum _{\beta =1}^d{x}_{i\beta }+ld}$$

$${\hat{\pi }}_k=\sum _{i=1}^N\frac{I[y_i=k]}{N}$$

Categorical Naive Bayes

In some cases, features $X_j\in \{1,....,K_j\}$ are nominal and have no explicit meaning for their numerical values. Thus, in this case, we can model the pmf of $j$th feature of $i$th example given $Y=y_i$ by categorical pmf:

$$p_{X_j|Y}(x_{ij}|y_i)=\prod _{k=1}^{K_j}{\mu }_{j{y}_{i}k}^{I[x_{ij}=k]}$$

The likelihood function is therefore:

$$L(\mathit{\theta };D)=\prod _{i=1}^{N}P(\mathbf{X},Y;\mathit{\theta })=\prod _{i=1}^N{\pi }_{y_i}\prod _{j=1}^d\prod _{k=1}^{K_j}{\mu }_{j{y}_{i}k}^{I[x_{ij}=k]}$$

subject to constraints:

$$\sum _{i=1}^K{\pi }_i=1$$

$$\sum _{k=1}^{K_j}{\mu }_{ijk}=1$$

The estimates are:

$${\hat{\mu }}_{jck}=\frac{\sum _{i=1}^{N}I[y_i=c]I[x_{ij}=k]+l}{\sum _{i=1}^{N}I[y_i=c]+l{K}_j}$$

Gaussian Naive Bayes

Suppose features are continuously distributed $X_j\in \mathbb{R}$, then we can use gaussian distribution to model the conditional distribution of feature:

$$f_{X_j|Y}(x_{ij}|Y=y_i;{\mu }_{j{y}_i},{\sigma }_{j{y}_i})=N({\mu }_{j{y}_i},{\sigma }_{j{y}_i})$$

Then by following similar procedure, we have ML estimates:

$${\hat{\mu }}_{jk}=\frac{1}{n_k}\sum _{i=1}^{N}I[y_i=k]x_{ij}$$

$${\hat{\sigma }}_{jk}^2=\frac{1}{n_k}\sum _{i=1}^{N}I[y_i=k](x_{ij}-{\hat{\mu }}_{jk}{)}^2$$

Where $n_c=\frac{1}{n_k}\sum _{i=1}^{N}I[y_i=k]$

Naive Bayes as Linear Classifier

Implementation

import pandas as pd
import numpy as np

class MultinomialNB:

    def __init__(self, alpha=1):
        self.alpha = alpha
        self.theta = None
        self.class_prior = None
        self.class_map = None

    def fit(self, X, y):
        if isinstance(X, pd.DataFrame):
            X = X.values

        if isinstance(y, pd.Series):
            y = y.values

        c_ = np.unique(y)
        n_c = c_.size
        NT, N_d = X.shape

        self.theta = np.zeros((n_c, N_d))
        self.class_prior = np.array(np.unique(y, return_counts=True), dtype=np.float64).T
        self.class_prior[:, 1] = self.class_prior[:, 1] / NT
        self.class_map = {}
        
        for index, c in enumerate(c_):
            N_c = X[y == c].sum()
            self.class_map[index] = c
            for i in range(N_d):
                N_ci = X[y == c, i].sum()
                self.theta[index, i] = np.log((N_ci + self.alpha) / (N_c + self.alpha * N_d))

        return self


    def predict(self, X):
        if isinstance(X, pd.DataFrame):
            X = X.values

        pred_results = np.zeros(X.shape[0])
        class_size = len(self.class_map)
        
        for index, i in enumerate(X):
            temp_lst = np.zeros(class_size)
            for c in range(class_size):
                temp_lst[c] = np.log(self.class_prior[:, 1][c])
                for d in range(X.shape[1]):
                    temp_lst[c] = temp_lst[c] + self.theta[c][d] * i[d]

            pred_results[index] = self.class_map[np.argmax(temp_lst)]

        return pred_results

Ref

http://www.cs.toronto.edu/~zemel/documents/2515/Tutorial4-2515-nb-gbc.pdf

https://mattshomepage.com/articles/2016/Jun/26/multinomial_nb/

https://classes.cec.wustl.edu/~SEAS-SVC-CSE517A/sp20/lecturenotes/06_lecturenote_NB.pdf