# bayesian classification unknown domain

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 ?

• AFAIK, Laplace smoothing doesn't require prior domain knowledge. It simply gives a 1 count to any term found in a new text (so that no zeros are introduced into probability calculations) -- as if the training set had one instance of the new term. It doesn't materially affect performance. Jul 24, 2016 at 12:15
• but by adding 1 to the count of that new item the probability of occurrence of each word would change, and for that probability to change, we need to know the domain because we are essentially dividing by sum of all occurrence counts plus k times our domain to get our probability matrix
– Imlerith
Jul 24, 2016 at 12:18
• Do I understand you correctly that you want your algorithm to work "online" with new inputs and learn from them..?
– Tim
Jul 25, 2016 at 8:53
• @Tim not really learn from new inputs... I just want my classifier to be resilient when it encounters new words Jul 25, 2016 at 10:21

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 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$.