Problème avec l'opération de précision en virgule flottante en C

Question

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

Maintenant, j'ai un problème pour implémenter l'algorithme en raison des limitations du type de données du C.

(algorithme J'utilise est donnée ici, http://en.wikipedia.org/wiki/Bayesian_spam_filtering)

PROBLÉMATIQUE: L'algorithme consiste à prendre chaque mot dans un document et calcul de la probabilité de celui-ci étant mot de spam. Si p1, p2 p3 .... pn sont des probabilités du mot-1, 2, 3 ... n. La probabilité de doc étant un spam ou non est calculée à l'aide

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 pour un 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é Float, double et même long double types de données, mais toujours le même problème. Donc, disons dans un document de 100K mots que j'analyse, si seulement 162 mots ont 1% de probabilité de spam et que 99838 sont des mots de spam, alors mon application le dira comme non Spam doc à cause de l'erreur Precision (comme le numérateur va facilement à ZERO) !!!

C'est la première fois que je suis confronté à ce problème. Alors, comment exactement ce problème devrait être abordé?

Answer 1

Votre problème est dû au fait que vous collectez trop de termes sans tenir compte de leur taille. Une solution consiste à prendre des logarithmes. Une autre consiste à trier vos termes individuels. D'abord, réécrivons l'équation comme 1/p = 1 + ∏((1-p_i)/p_i). Maintenant, votre problème est que certains termes sont petits, tandis que d'autres sont grands. Si vous avez trop de petits termes dans une rangée, vous déborderez, et avec trop de gros termes vous déborderez le 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-débit. Mais l'ordre de calcul n'a pas d'importance. Utilisez deux itérateurs dans votre collection temporaire. L'un commence au début (c'est-à-dire (1-p_0)/p_0), l'autre à la fin (c'est-à-dire (1-p_n)/p_n) et votre résultat intermédiaire commence à 1.0. Maintenant, quand votre résultat intermédiaire est> = 1.0, vous prenez un terme à l'avant, et quand votre résultat intermédiaire est < 1.0, vous prenez un résultat à l'arrière.

Le résultat est que lorsque vous prenez des termes, le résultat intermédiaire oscillera autour de 1,0. Il ne va monter ou descendre que lorsque vous êtes à court ou à long terme. Mais ça va. À ce stade, vous avez consommé les extrêmes aux deux extrémités, de sorte que le résultat intermédiaire approche lentement le résultat final.

Il y a bien sûr une réelle possibilité de débordement. Si l'entrée est complètement improbable d'être un spam (p = 1E-1000) alors 1/p débordera, car ∏((1-p_i)/p_i) déborde. Mais puisque les termes sont triés, nous savons que le résultat intermédiaire débordera seulement 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 subséquente.

Answer 2

Vous pouvez utiliser les probabilités ou en pourcents ProMiles:

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

ou

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

ou utiliser un autre coefficient

Answer 3

Cela arrive souvent dans l'apprentissage de la machine. AFAIK, il n'y a rien que vous pouvez faire sur la perte de précision. Donc, pour contourner ceci, nous utilisons la fonction log et convertissons les divisions et les multiplications en soustractions et additions, resp.

SO I a décidé de faire le calcul,

L'équation d'origine est:

je modifie légèrement le:

Prenant billes des deux côtés:

Let,

substituant

où la formule de remplacement pour le calcul de la probabilité combinée:

Si vous avez besoin de moi pour développer cela, s'il vous plaît laissez un commentaire.

Answer 4

Je ne suis pas forte en maths donc je ne peux pas commenter sur les simplifications possibles à la formule qui pourraient éliminer ou réduire votre problème. Cependant, je connais les limites de précision de longs types doubles et je suis au courant de plusieurs bibliothèques de mathématiques de précision arbitraires et prolongées pour C. Départ:

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

Answer 5

Essayez 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 avez un petit nombre de les valeurs qui se reproduisent - vous pouvez utiliser la fonction pow() - pow (1-p, occurences_of_p) * pow (1-q, occurrences_of_q) - et éviter l'arrondi individuel à chaque multiplication.

Answer 6

Voici une astuce:

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 importants (entre 0 et, pour p_i = 0.01, 99). L'idée est, non pas de multiplier des tonnes de petits nombres entre eux, d'obtenir, 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 triés et vous les jumeler pour opposition (supposons p_1 < ... < p_n), la formule suivante sera encore meilleure précision:

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

cette façon, vous diviser grands numérateurs (petit p_i) avec de grands dénominateurs (grand p_(n+1-i)), et de petits numérateurs avec de petits dénominateurs.

modifier: 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)