Naive Bayes

Bayes Theorem¶

Bayes’ Theorem:
Update your belief when you have new evidence.

• In classification,

  $$P(Y=k | X=x) = \frac{\pi_kf_k(x)}{\sum_{l=1}^K\pi_lf_l(x)}$$

  (2)

• $P(Y=k|X=x)$: Posterior probability.

  • “Given I observed this data point $x$, what is the probability that it belongs to class $k$?”

  • We want to find out the class $k$ that maximizes this probability.

  • The goal is to predict class $k$ that maximizes the posterior probability: $\arg\max_{k} \left( \pi_k \prod_{j=1}^{p} f_{kj}(x_j) \right)$

  • Equation can be written this way because we can ignore the denominator as the denominator will be a constant.

• $\pi_k$: Prior probability of class $k$.

  • How common class $k$ is in the population before seeing any data.

  • If 70% of training data is labeled as class A, then $\pi_\text{A} = 0.7$.

• $f_k(x)$: Likelihood.

  • $f_k(X) = P(X=x|Y=k)$: Also called as conditional density.

  • Given that a point belongs to class $k$, how probable is it to look like $x$ (how typical is this data point)?

  • For the Gaussian version, assume that the density is multivariate Gaussian with diagonal covariance. If class $k$ has a Gaussian distribution, $f_k(x)$ is just the Gaussian PDF evaluated at $x$.

• $\sum_{l=1}^{K} \pi_l f_l(x)$: Sums over all $K$ classes. Normalizing constant that ensures all postieror probabilities across classes sum to 1.

Assumption¶

• We assume that conditional on class $k$, variables $x_j$ are independent. Hence we multiply the conditional density of each variable to get the joint density:

  $$f_k(X) = \prod_{j=1}^{p} f_{kj}(x_j)$$

  (3)

• When combined with Bayes Theorem:

  $$P(Y = k \mid X = x) = \frac{\pi_k f_k(x)}{\sum_{l=1}^{K} \pi_l f_l(x)} = \frac{\pi_k \prod_{j=1}^{p} f_{kj}(x_j)}{\sum_{l=1}^{K} \left( \pi_l \prod_{j=1}^{p} f_{lj}(x_j) \right)}$$

  (4)

• When $X$ has many features with $p$-dimensions, estimating $f_k(x)$ as a full multivariate Gaussian is expensive and requires a lot of data. So in naive bayes, we pretend that all features are independent of each other within each class.

  • Hence, conditional on the outcome, there is no muilticollinearity.

  • Once you already know the class, Naive Bayes only requires the features to be independent.

  • $x_1$ and $x_2$ are independent given $Y=k$.

• When there are many features, multiplying lots of small number together to achieve $f_k(X) = \prod_{j=1}^{p} f_{kj}(x_j)$ causes numerical underflow; product becomes so small that gets rounded up to zero and everything beraks.

  • This problem can be avoided by taking log transformation and turn product into a sum.

    $$\text{log} f_k(x) = \sum^p_{j=1} \log f_{kj}(x_j)$$

    (7)

  • Because log function is monotone, taking the log does not change the class $k$ that yields the maximum posterior probability.

Conditional independence is within a class¶

Two features can be associated in the full sample even when they are independent within each class. For example, two words may both occur more often in one document class. Their overall association can come from the mixture of classes.

The assumption is stronger than zero correlation: knowing one feature must give no additional information about another after conditioning on the class. It is a modeling assumption, not something that preprocessing automatically makes true. Duplicate features count the same evidence twice and can make the posterior too extreme.

For classification, use the log score

The prior must remain in this score. Only the denominator shared by all classes can be dropped when choosing the largest score.

Estimation¶

• Estimation means computing the parameters of a model from training data since we don’t know the true values.

• In Naive Bayes, estimate the prior probability from training data. Also called as proportional prior.

• Called proportional because it’s just the proportion of each class in the training data.

Categorical Variable¶

• If the $x$-variable is categorical, density is a probability.

Continuous Variable¶

• Estimate probability from a marginal density.

  $$f_{kj}(x_j) = \frac{1}{\sqrt{2\pi\sigma_{jk}^2}} \exp\left[-\frac{1}{2}\left(\frac{x_j - \mu_{jk}}{\sigma_{jk}}\right)^2\right]$$

  (15)

• Typically, Gaussian distribution is assumed. In this case, it is called as Gaussian Naive Bayes.

LaPlace Smoothing¶

Zero Probability Problem¶

When you estimate probabilities from training data using $\frac{n_{kj}}{n_k}$, you often get a probability of 0 if a particular feature never appears in class $k$.

So, one single 0 can wipe out the entire product and ignore evidence from all other features.

Intuition¶

LaPlace smoothing adds a small count (usually 1) to every possible value, pretending that there is at leaset one count.

• $V$ refers to the number of catgories of the corresponding $x$-variable.

• Data above gets transformed to:

• For county, add $d_j = 5$ for each $y$ category (in the denominator).

Generalized LaPlace Estimator¶

• Instead of adding 1 count, we can add an arbitrary number of observations, $L$, that controls the amount of shrinking.

  $$P(X_j = x_j \mid Y = k) = \frac{n_{kj} + L}{n_k + L * d_j}$$

  (27)

• If $L$ is very large, it gets summarized to $P(X_j = x_j \mid Y = k) = \frac{1}{d_j}$.

• $L$ can be choosen by minimizing error on validation data.

• $L$ does not have to be an integer value.

Choosing the feature distribution¶

• Gaussian Naive Bayes models a continuous feature with a class-specific mean and variance. The density value is not the probability of observing one exact real number.

• Bernoulli Naive Bayes models binary presence or absence. Absence contributes to the likelihood as well as presence.

• Multinomial Naive Bayes models token counts within a document. Repeated words contribute repeatedly, and smoothing uses total token counts in the class as the denominator base, rather than the number of documents.

The categorical smoothing formula above applies to one categorical feature at a time. Adding $L$ to each of its $d_j$ categories adds $Ld_j$ to the denominator, keeping the probabilities summed to 1.

Class priors also matter. If training observations were deliberately balanced by sampling equal numbers from each class, the sample proportions may not represent the population where predictions will be made. Interpret posterior probabilities with that sampling scheme in mind.