bayesian classification unknown domain

Question

Suppose I am building a naive Bayes model to classify text messages as either spam or legit.

I am training my model using a dataset containing both classes and for which I know the domain (the number of possible words)

Obviously, when I will deploy or validate my model, it will encounter new words that occurred 0 times in the training dataset.

Using Laplace smoothing (adding all counts by k and dividing by the sum of all occurrence counts plus k times our domain), I can avoid having 0 conditional probabilities

However, since the domain will not always be known, should my model increment the count matrix and apply smoothing each time it encounters a new word? wouldn't that be bad performance wise? Is there an alternative to Laplace smoothing that doesn't require a prior knowledge of the domain ?

Answer 1

It is a common problem that in natural language data you do not observe some values that possibly can occur (e.g. you count frequencies of letters and in your data some uncommon letter does not occur at all). In this case the classical estimator for probability, i.e.

$$ \hat p = \frac{n_i}{\sum_i n_i} $$

where $n_i$ is a number of occurrences of $i$th value (out of $d$ categories), gives you $\hat p = 0$ if $n_i = 0$. This is called zero-frequency problem. For such values you know that their probability is nonzero (they exist!), so this estimate is obviously incorrect. There is also a practical concern: multiplying and dividing by zeros leads to zeros or undefined results, so zeros are problematic in dealing with.

The easy and commonly applied fix is, to add some constant $\beta$ to your counts, so that

$$ \hat p = \frac{n_i + \beta}{(\sum_i n_i) + d\beta} $$

The common choice for $\beta$ is $1$, i.e. applying uniform prior based on Laplace's rule of succession, $1/2$ for Krichevsky-Trofimov estimate, or $1/d$ for Schurmann-Grassberger (1996) estimator. Notice however that what you do here is you apply out-of-data (prior) information in your model, so it gets subjective, Bayesian flavor. With using this approach you have to remember of assumptions you made and take them into consideration. The fact that we have strong a priori knowledge that there should not be any zero probabilities in our data directly justifies the Bayesian approach in here.

This approach is commonly used, e.g. in R enthropy package. You can find some further information in the following paper:

Schurmann, T., and P. Grassberger. (1996). Entropy estimation of symbol sequences. Chaos, 6, 41-427.

In your case...

In practice the correction is used by adding some constant $\beta$ to your training data, then when using your model for prediction, you add $\beta$ to the counts in the newly encountered data. So if $n_i$ is a count of numbers you have seen $i$-th word, then it becomes $n_i + \beta$. If you haven't encountered $i$-th word yet, then it is simply $\beta$. You do not re-calculate the weights for all the words each time a new word is seen in your data. For every $i$-th word you add $\beta$ only once, so all the counts are elevated by the same factor $\beta$.

---

_{Disclosure: This answer uses parts of answer for the other question that I provided earlier (that is not-obvious to find while searching for this topic).}