Problema con funzionamento in virgola mobile di precisione in C

Question

Per uno dei miei progetti di corso ho iniziato a implementare "classificatore bayesiano di Naive" in C. Il mio progetto consiste nell'implementare un'applicazione di classificazione di documenti (in particolare spam) utilizzando enormi dati di addestramento.

Ora ho problemi nell'implementare l'algoritmo a causa delle limitazioni nel tipo di dati del C.

(Algoritmo sto usando è dato qui, http://en.wikipedia.org/wiki/Bayesian_spam_filtering)

problema dichiarazione: L'algoritmo consiste nel prendere ogni parola in un documento e calcolando la probabilità di esso che è parola spam. Se p1, p2 p3 .... pn sono le probabilità della parola-1, 2, 3 ... n. La probabilità di essere doc spam o non viene calcolato utilizzando

Qui, valore di probabilità può essere molto facilmente intorno 0.01. Quindi, anche se uso il tipo di dati "double", il mio calcolo andrà a finire. Per confermare questo ho scritto un codice di esempio indicato di seguito.

#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; 
} 

ho provato float, double e anche lunghi tipi di dati double, ma ancora lo stesso problema.

Quindi, diciamo in un documento di 100K parole che sto analizzando, se solo 162 parole hanno l'1% di probabilità di spam e 99838 rimanenti sono vistosamente parole di spam, quindi la mia app lo dirà come Not Spam doc a causa di errore di precisione (come numeratore facilmente va a ZERO) !!!.

Questa è la prima volta che sto riscontrando questo problema. Quindi, come esattamente dovrebbe essere affrontato questo problema?

Answer 1

Il tuo problema è causato dal fatto che stai raccogliendo troppi termini senza riguardo per le loro dimensioni. Una soluzione è prendere i logaritmi. Un altro è per ordinare i tuoi termini individuali. Innanzitutto, riscriviamo l'equazione come 1/p = 1 + ∏((1-p_i)/p_i). Ora il tuo problema è che alcuni termini sono piccoli, mentre altri sono grandi. Se hai troppi termini di piccole dimensioni in una riga, subirai un underflow e con troppi termini dovrai sovradimensionare il risultato intermedio.

Quindi, non mettere troppi dello stesso ordine di seguito. Ordina i termini (1-p_i)/p_i. Di conseguenza, il primo sarà il termine più piccolo, l'ultimo il più grande. Ora, se li moltiplicassi subito avresti comunque un underflow. Ma l'ordine di calcolo non ha importanza. Usa due iteratori nella tua collezione temporanea. Uno inizia all'inizio (ad esempio (1-p_0)/p_0), l'altro alla fine (ovvero (1-p_n)/p_n) e il risultato intermedio inizia da 1.0. Ora, quando il tuo risultato intermedio è> = 1.0, prendi un termine dalla parte anteriore, e quando il tuo risultato intemedio è < 1.0 prendi un risultato dal retro.

Il risultato è che mentre si prendono i termini, il risultato intermedio oscillerà intorno a 1.0. Andrà solo su o giù mentre si esauriscono termini piccoli o grandi. Ma va bene. A quel punto, hai consumato gli estremi su entrambe le estremità, quindi il risultato intermedio si avvicina lentamente al risultato finale.

C'è ovviamente una possibilità reale di overflow. Se è improbabile che l'input sia spam (p = 1E-1000), l'1/p verrà in overflow perché overflow ∏((1-p_i)/p_i). Ma dal momento che i termini sono ordinati, sappiamo che il risultato intermedio sarà overflow solo se overflow ∏((1-p_i)/p_i). Quindi, se il risultato intermedio trabocca, non c'è alcuna successiva perdita di precisione.

Answer 2

È possibile utilizzare probabilità in percentuale o promiles:

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

o

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

o usare qualche altro coefficiente

Answer 3

Questo accade spesso nel machine learning. AFAIK, non c'è niente che puoi fare per la perdita di precisione. Quindi per aggirare questo, usiamo la funzione log e convertiamo divisioni e moltiplicazioni in sottrazioni e aggiunte, risp.

così ho deciso di fare la matematica,

L'equazione originale è:

ho modificare leggermente esso:

Prendendo i registri su entrambi i lati:

Let,

Sostituendo,

qui la formula alternativa per calcolare la probabilità combinata:

Se hai bisogno di me per espandere questo, si prega di lasciare un commento.

Answer 4

Non sono forte in matematica, quindi non posso commentare le possibili semplificazioni alla formula che potrebbe eliminare o ridurre il problema. Tuttavia, mi è familiare con le limitazioni di precisione di lunghe tipi doppie e sono a conoscenza di diverse librerie matematiche precisione arbitraria ed estese per C. Controlla per:

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

Answer 5

Prova calcolando l'inverso 1/p . Questo ti dà un'equazione del modulo 1 + 1/(1-p1) * (1-p2) ...

Se poi conti il ​​verificarsi di ogni probabilità - sembra che tu abbia un piccolo numero di valori che si ripetono - puoi usare la funzione pow() - pow (1-p, occurrences_of_p) * pow (1-q, occorrenze_di_q) - ed evitare arrotondamenti individuali con ogni moltiplicazione.

Answer 6

Ecco un trucco:

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) 

Quindi, fondamentalmente, si otterrà un prodotto di abbastanza grandi numeri (tra 0 e, per p_i = 0.01, 99). L'idea è di non moltiplicare tonnellate di numeri piccoli l'uno con l'altro per ottenere, beh, 0, ma per fare un quoziente di due piccoli numeri. Ad esempio, se n = 1000000 and p_i = 0.5 for all i, il metodo sopra ti darà 0/(0+0) che è NaN, mentre il metodo proposto ti darà 1/(1+1*...1), che è 0.5.

è possibile ottenere risultati ancora migliori, quando tutti p_i sono ordinati e li accoppiare in modo opposto (supponiamo p_1 < ... < p_n), quindi la seguente formula otterrà ancora meglio di precisione:

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

in questo modo si Dividere numeratori grandi (piccolo p_i) con denominatori grandi (grande p_(n+1-i)) e numeratori piccoli con denominatori piccoli.

modifica: MSalter ha proposto un'utile ulteriore ottimizzazione nella sua risposta. Usandolo, la formula è la seguente:

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)