2
$\begingroup$

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 ?

$\endgroup$

migrated from stackoverflow.com Jul 24 '16 at 12:55

This question came from our site for professional and enthusiast programmers.

  • $\begingroup$ 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. $\endgroup$ – lawyeR Jul 24 '16 at 12:15
  • $\begingroup$ 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 $\endgroup$ – Imlerith Jul 24 '16 at 12:18
  • $\begingroup$ Do I understand you correctly that you want your algorithm to work "online" with new inputs and learn from them..? $\endgroup$ – Tim Jul 25 '16 at 8:53
  • $\begingroup$ @Tim not really learn from new inputs... I just want my classifier to be resilient when it encounters new words $\endgroup$ – Imlerith Jul 25 '16 at 10:21
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I am keeping both a count matrix and its corresponding probability matrix which is essentially another matrix with all the counts divided by the row sum. this is why I talked about updating the weights. However, after reading your input, I believe that might not have been the correct way of doing this. I will also look into the alternatives your proposed I believe one them is referred to as m-estimate ? $\endgroup$ – Imlerith Jul 25 '16 at 10:41
  • $\begingroup$ @Imlerith I do not recall seeing it under such name. $\endgroup$ – Tim Jul 25 '16 at 11:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.