I am in the midst of programming a simple Naive Bayes classifier as an exercise. It is supposed to perform word-sense disambiguation on natural language phrases, e.g. predicting the correct meaning of the ambiguous word bass in a sentence like I love the taste of bass.

At the moment I am struggling with handling discrete features potentially assuming one of infinitely many values (i.e. features assuming values from countably infinite domains). An example for such a feature might be the length of the preceding word. In the example above, the feature value would be 2, as the word preceding bass has this many characters.

The root of my problem is that in some languages (maybe not in English, but certainly in other languages as for instance German) one can form new words of arbitrary length by concatenating an arbitrary number of already existing words (the linguistic term for this process is compounding). For example, the three German words Fußball (football), Schuh (shoe) and Schnürsenkel (laces) make up the valid compound Fußballschuhschnürsenkel.

That is, the domain of the feature "Length of the preceding word" is the set of natural numbers (including 0 for observations where the target word is the first word in the sentence), i.e. it is countably infinite. If I decided to use this feature, the classifier during training would have to determine the distribution for the probability $P(L_p = l_p|W = w)$. That is to say, given a target word $w$, how probable is it that the length of the previous word is equal to $l_p$.

Afterwards, when classifying input sentences or phrases, it can happen that due to data sparseness no probability for a certain $(L_p, W)$ pair could be determined during training. For example, it might happen that in an input sentence the target word (bass in the above example) is preceded by a very long word (e.g. 30 characters), but that in the training data no such cases were present, i.e. the probability $P(L_p = 30 | W = bass)$ would be zero.

Facing the issue of zero values described above, it is necessary to avoid them by using an appropriate kind of smoothing. Obviously, not all established smoothing methods are applicable in such a case. For instance, the widely used add-one smoothing which transforms a probability $n_{F=v}/N$ into $(n_{F=v}+1)/(N+B)$ (where $n_{F=v}$ is the number of observed situations in which feature $F$ assumes the value $v$, $N$ is the total amount of observations and $B$ is the number of values that feature $F$ can assume) would fail in this case as $B$ would be $\infty$ (since the number of values $F$ can assume is unbounded because the preceding word can have any length).

The considerations above, finally, lead me to the following question: What smoothing methods are there to deal with features assuming values from countably infinite domains?


Your Answer

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

Browse other questions tagged or ask your own question.