Naive Bayes Classifier

The Bayes-optimal (MAP) classifier, the naive conditional-independence assumption and why it makes learning tractable, parameter estimation by counting, worked spam example, zero counts and Laplace smoothing, Bernoulli, multinomial and Gaussian variants, log-space computation, and strengths and weaknesses.

The Bayes classifier

Given features $\mathbf x$ , predict the class with the largest posterior probability (the MAP rule from Bayes' theorem):

\hat y = \arg\max_y P(y \mid \mathbf x) = \arg\max_y P(\mathbf x\mid y)\,P(y).

This Bayes-optimal rule minimises the error rate — if we knew the true distributions. The difficulty is estimating $P(\mathbf x\mid y)$ : with $d$ binary features the joint distribution has $2^d - 1$ parameters per class.

The naive assumption

Assume the features are conditionally independent given the class:

P(x_1, \dots, x_d\mid y) = \prod_{j=1}^dP(x_j\mid y) \quad\Longrightarrow\quad \hat y = \arg\max_y\ P(y)\prod_{j=1}^dP(x_j\mid y).

Now each $P(x_j \mid y)$ is a one-dimensional distribution estimated by simple counting. Parameters grow linearly in $d$ instead of exponentially.

The class causes each feature; given the class, features carry no information about each other.

Training = counting

Quantity	Estimate
Prior $P(y = c)$	fraction of training examples in class $c$
Categorical feature $P(x_j = v\mid c)$	$\dfrac{\#(x_j = v, y = c)}{\#(y = c)}$
Multinomial word probability $P(w\mid c)$	$\dfrac{\text{count of } w \text{ in class } c}{\text{total words in class } c}$
Gaussian feature	class mean $\mu_{jc}$ and variance $\sigma^2_{jc}$

Training is a single pass over the data: $O(nd)$ .

Zero counts and Laplace smoothing

If a feature value never occurs with a class in training, its estimate is 0 and wipes out the entire product. Laplace (add- $\alpha$ ) smoothing:

P(x_j = v\mid c) = \frac{\#(x_j = v, c) + \alpha}{\#(c) + \alpha\,k_j},

where $k_j$ is the number of possible values of $x_j$ (vocabulary size $\lvert V\rvert$ for words). $\alpha = 1$ is add-one smoothing.

Variants

Variant	Features	Likelihood
Bernoulli NB	binary (word present/absent)	$\prod_j p_{jc}^{x_j}(1 - p_{jc})^{1 - x_j}$ — absent words count too
Multinomial NB	counts (word frequencies)	$\prod_w P(w\mid c)^{n_w}$
Gaussian NB	continuous	$\prod_j\frac{1}{\sqrt{2\pi}\sigma_{jc}}\exp\left(-\frac{(x_j - \mu_{jc})^2}{2\sigma_{jc}^2}\right)$

Log space: compute $\log P(y) + \sum_j\log P(x_j\mid y)$ to avoid underflow. Multinomial and Bernoulli NB are then linear classifiers in the features (log-probabilities act as weights).

Strengths and weaknesses

Strengths	Weaknesses
very fast to train and predict, scales to huge vocabularies	the independence assumption is usually false
works with little data; few parameters	probability estimates are poorly calibrated (overconfident) when features are correlated
handles many features and missing values gracefully	correlated features are effectively double-counted
strong baseline for text (spam, sentiment, topic)	outperformed by discriminative models with enough data

Naive Bayes often classifies well even when its probabilities are off, because only the ranking of the classes matters for the decision.