Problème avec le fonctionnement en virgule flottante Precision en C

Pour l’un de mes projets de cours, j’ai commencé à implémenter un “classificateur naïf bayésien” en C. Mon projet consiste à implémenter une application de classificateur de documents (en particulier Spam) utilisant d’énormes données d’apprentissage.

Maintenant, j’ai du mal à implémenter l’algorithme à cause des limitations du type de données du C.

(L’algorithme que j’utilise est donné ici, http://en.wikipedia.org/wiki/Bayesian_spam_filtering )

DÉCLARATION DU PROBLÈME: L’algorithme consiste à prendre chaque mot d’un document et à calculer la probabilité qu’il s’agisse d’un mot spam. Si p1, p2 p3 …. pn sont des probabilités du mot-1, 2, 3 … n. La probabilité que le document soit spam ou non est calculée à l’aide de

texte alternatif

Ici, la valeur de probabilité peut être très facilement autour de 0,01. Donc, même si j’utilise le type de données “double”, mon calcul ira au tirage au sort. Pour confirmer cela, j’ai écrit un exemple de code donné ci-dessous.

#define PROBABILITY_OF_UNLIKELY_SPAM_WORD (0.01) #define PROBABILITY_OF_MOSTLY_SPAM_WORD (0.99) int main() { int index; long double numerator = 1.0; long double denom1 = 1.0, denom2 = 1.0; long double doc_spam_prob; /* Simulating FEW unlikely spam words */ for(index = 0; index < 162; index++) { numerator = numerator*(long double)PROBABILITY_OF_UNLIKELY_SPAM_WORD; denom2 = denom2*(long double)PROBABILITY_OF_UNLIKELY_SPAM_WORD; denom1 = denom1*(long double)(1 - PROBABILITY_OF_UNLIKELY_SPAM_WORD); } /* Simulating lot of mostly definite spam words */ for (index = 0; index < 1000; index++) { numerator = numerator*(long double)PROBABILITY_OF_MOSTLY_SPAM_WORD; denom2 = denom2*(long double)PROBABILITY_OF_MOSTLY_SPAM_WORD; denom1 = denom1*(long double)(1- PROBABILITY_OF_MOSTLY_SPAM_WORD); } doc_spam_prob= (numerator/(denom1+denom2)); return 0; } 

J’ai essayé les types de données Float, doubles et même longs doubles, mais toujours le même problème.

Par conséquent, disons dans un document de 100 000 mots que j’parsing, si 162 mots seulement ont une probabilité de 1% de spam et 99838 restants sont des mots de spam bien en évidence, mon application le dira quand même comme non-spam par erreur de précision (le numérateur passe facilement) à zéro) !!!

C’est la première fois que je frappe un tel problème. Alors, comment aborder ce problème au juste?

Votre problème est dû au fait que vous collectez trop de termes sans vous soucier de leur taille. Une solution consiste à prendre des logarithmes. Une autre consiste à sortinger vos termes individuels. Tout d’abord, réécrivons l’équation comme suit: 1/p = 1 + ∏((1-p_i)/p_i) . Maintenant, votre problème est que certains termes sont petits, alors que d’autres sont volumineux. Si vous avez trop de petits termes dans une rangée, vous allez sous-déborder et avec trop de gros termes, vous déborderez du résultat intermédiaire.

Donc, ne mettez pas trop du même ordre dans une rangée. Triez les termes (1-p_i)/p_i . En conséquence, le premier sera le plus petit terme, le dernier le plus grand. Maintenant, si vous les multipliez tout de suite, vous aurez toujours un sous-stream. Mais l’ordre de calcul n’a pas d’importance. Utilisez deux iterators dans votre collection temporaire. L’une commence au début (c’est (1-p_0)/p_0 dire (1-p_0)/p_0 ), l’autre à la fin (c’est (1-p_n)/p_n dire (1-p_n)/p_n ) et votre résultat intermédiaire commence à 1.0 . Désormais, lorsque votre résultat intermédiaire est> = 1.0, vous prenez un terme de l’avant et lorsque votre résultat intermédiaire est <1.0, vous prenez un résultat de l'arrière.

Le résultat est que, comme vous le dites, le résultat intermédiaire oscillera autour de 1,0. Il ne fera que monter ou descendre quand vous serez à court de gros ou de gros termes. Mais ça va. À ce stade, vous avez consommé les extrêmes aux deux extrémités, de sorte que le résultat intermédiaire se rapproche lentement du résultat final.

Il existe bien sûr une possibilité réelle de débordement. S’il est totalement peu probable que l’entrée soit du spam (p = 1E-1000), 1/p débordera, car ∏((1-p_i)/p_i) débordera. Mais comme les termes sont sortingés, nous soaps que le résultat intermédiaire ne débordera que si ∏((1-p_i)/p_i) déborde. Donc, si le résultat intermédiaire déborde, il n’y a pas de perte de précision ultérieure.

Cela arrive souvent dans l’apprentissage automatique. Autant que je sache, vous ne pouvez rien faire contre la perte de précision. Donc, pour contourner cela, nous utilisons la fonction log et convertissons les divisions et les multiplications en soustractions et additions, resp.

Alors j’ai décidé de faire le calcul,

L’équation originale est:

Problème

Je le modifie légèrement:

entrez la description de l'image ici

Prendre des journaux des deux côtés:

entrez la description de l'image ici

Laisser,

entrez la description de l'image ici

En remplaçant,

entrez la description de l'image ici

D’où la formule alternative pour calculer la probabilité combinée:

entrez la description de l'image ici

Si vous avez besoin de moi pour développer, veuillez laisser un commentaire.

Voici un truc:

 for the sake of readability, let S := p_1 * ... * p_n and H := (1-p_1) * ... * (1-p_n), then we have: p = S / (S + H) p = 1 / ((S + H) / S) p = 1 / (1 + H / S) let`s expand again: p = 1 / (1 + ((1-p_1) * ... * (1-p_n)) / (p_1 * ... * p_n)) p = 1 / (1 + (1-p_1)/p_1 * ... * (1-p_n)/p_n) 

Donc, fondamentalement, vous obtiendrez un produit de nombres assez grands (entre 0 et, pour p_i = 0.01 , 99 ). L’idée est, non pas de multiplier des tonnes de petits nombres les uns avec les autres, pour obtenir, eh bien, 0 , mais de faire un quotient de deux petits nombres. Par exemple, si n = 1000000 and p_i = 0.5 for all i , la méthode ci-dessus vous donnera 0/(0+0) qui est NaN , alors que la méthode proposée vous donnera 1/(1+1*...1) , qui est 0.5 .

Vous pouvez obtenir des résultats encore meilleurs lorsque tous les p_i sont sortingés et que vous les associez dans un ordre opposé (supposons que p_1 < ... < p_n ), la formule suivante obtiendra une précision encore meilleure:

  p = 1 / (1 + (1-p_1)/p_n * ... * (1-p_n)/p_1) 

De cette façon, vous séparez les grands numérateurs (petits p_i ) avec des grands dénominateurs (grands p_(n+1-i) ) et des petits numérateurs avec des petits dénominateurs.

edit: MSalter a proposé une optimisation supplémentaire utile dans sa réponse. En l'utilisant, la formule se lit comme suit:

  p = 1 / (1 + (1-p_1)/p_n * (1-p_2)/p_(n-1) * ... * (1-p_(n-1))/p_2 * (1-p_n)/p_1) 

Essayez de calculer l’inverse 1 / p. Cela vous donne une équation de la forme 1 + 1 / (1-p1) * (1-p2) …

Si vous comptez ensuite l’occurrence de chaque probabilité – il semble que vous ayez un petit nombre de valeurs récurrentes – vous pouvez utiliser la fonction pow () – pow (1-p, occurences_of_p) * pow (1-q, occurrences_of_q) – et évitez les arrondis individuels à chaque multiplication.

Vous pouvez utiliser la probabilité en pourcentages ou promiles:

 doc_spam_prob= (numerator*100/(denom1+denom2)); 

ou

 doc_spam_prob= (numerator*1000/(denom1+denom2)); 

ou utiliser un autre coefficient

Je ne suis pas fort en mathématiques, je ne peux donc pas commenter d’éventuelles simplifications de la formule qui pourraient éliminer ou réduire votre problème. Cependant, je connais les limitations de précision des types doubles longs et suis conscient de plusieurs bibliothèques mathématiques de précision arbitraire et étendue pour C. Consultez:

http://www.nongnu.org/hpalib/ et http://www.tc.umn.edu/~ringx004/mapm-main.html