Vấn đề với hoạt động điểm chính xác trong C

Question

Đối với một trong các dự án khóa học của tôi, tôi bắt đầu thực hiện "Naive Bayesian classifier" trong C. Dự án của tôi là triển khai ứng dụng trình phân loại tài liệu (đặc biệt là Spam).

Bây giờ tôi gặp sự cố khi triển khai thuật toán vì các hạn chế trong kiểu dữ liệu của C.

(Algorithm Tôi đang sử dụng được đưa ra ở đây, http://en.wikipedia.org/wiki/Bayesian_spam_filtering)

VẤN ĐỀ BÁO CÁO: Thuật toán bao gồm việc uống mỗi từ trong một tài liệu và tính toán khả năng nó là từ thư rác. Nếu p1, p2 p3 .... pn là xác suất của từ-1, 2, 3 ... n. Xác suất của doc là spam hoặc không được tính bằng

Ở đây, giá trị xác suất có thể rất dễ dàng xung quanh 0,01. Vì vậy, ngay cả khi tôi sử dụng datatype "gấp đôi" tính toán của tôi sẽ đi cho một quăng. Để xác nhận điều này tôi đã viết một mã mẫu được đưa ra dưới đây.

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

Tôi đã thử các kiểu dữ liệu kép nổi, đôi và thậm chí dài nhưng vẫn gặp vấn đề tương tự.

Do đó, hãy nói trong tài liệu 100K từ tôi đang phân tích, nếu chỉ 162 từ có xác suất spam 1% và 99838 là từ spam rõ ràng, thì ứng dụng của tôi sẽ nói là Không phải spam vì lỗi chính xác (như tử số dễ dàng đi đến ZERO) !!!.

Đây là lần đầu tiên tôi gặp sự cố như vậy. Vậy vấn đề này sẽ được giải quyết như thế nào?

Answer 1

Vấn đề của bạn là do bạn đang thu quá nhiều cụm từ không liên quan đến kích thước của chúng. Một giải pháp là lấy logarit. Khác là để sắp xếp các điều khoản cá nhân của bạn. Trước tiên, hãy viết lại phương trình như 1/p = 1 + ∏((1-p_i)/p_i). Bây giờ vấn đề của bạn là một số thuật ngữ nhỏ, trong khi những thuật ngữ khác thì lớn. Nếu bạn có quá nhiều cụm từ nhỏ trong một hàng, bạn sẽ bị tràn và với quá nhiều cụm từ lớn, bạn sẽ tràn qua kết quả trung gian.

Vì vậy, không đặt quá nhiều thứ tự trong cùng một hàng. Sắp xếp các điều khoản (1-p_i)/p_i. Kết quả là, chữ đầu tiên sẽ là chữ nhỏ nhất, chữ cái cuối cùng lớn nhất. Bây giờ, nếu bạn nhân chúng ngay lập tức bạn vẫn sẽ có một dòng chảy. Nhưng thứ tự tính toán không quan trọng. Sử dụng hai trình vòng lặp vào bộ sưu tập tạm thời của bạn. Một cái bắt đầu ngay từ đầu (tức là (1-p_0)/p_0), cái kia ở cuối (ví dụ: (1-p_n)/p_n) và kết quả trung gian của bạn bắt đầu tại 1.0. Bây giờ, khi kết quả trung gian của bạn là> = 1.0, bạn lấy một từ ở phía trước và khi kết quả intemediate của bạn là < 1.0, bạn lấy kết quả từ phía sau.

Kết quả là khi bạn thực hiện các điều khoản, kết quả trung gian sẽ dao động khoảng 1.0. Nó sẽ chỉ đi lên hoặc xuống khi bạn chạy ra khỏi các điều khoản nhỏ hoặc lớn. Nhưng đó là OK. Tại thời điểm đó, bạn đã tiêu thụ các cực trên cả hai đầu, do đó, kết quả trung gian sẽ dần dần tiếp cận kết quả cuối cùng.

Tất nhiên là có khả năng xảy ra tràn. Nếu đầu vào hoàn toàn không thể là spam (p = 1E-1000) thì 1/p sẽ tràn, vì ∏((1-p_i)/p_i) tràn. Tuy nhiên, vì các cụm từ được sắp xếp, chúng tôi biết rằng kết quả trung gian sẽ tràn chỉ chỉ nếu một số dòng bị tràn qua ∏((1-p_i)/p_i). Vì vậy, nếu kết quả trung gian tràn, không có sự mất chính xác tiếp theo.

Answer 2

Bạn có thể sử dụng xác suất trong phần trăm hoặc promiles:

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

hoặc

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

hoặc sử dụng một số hệ số khác

Answer 3

Điều này xảy ra thường xuyên trong học máy. AFAIK, không có gì bạn có thể làm về sự mất mát về độ chính xác. Vì vậy, để bỏ qua điều này, chúng tôi sử dụng chức năng log và chuyển đổi các bộ phận và phép nhân thành phép trừ và bổ sung, resp.

SO tôi quyết định làm toán,

Phương trình ban đầu là:

Tôi hơi sửa đổi nó:

Lấy bản ghi trên cả hai mặt:

Lết,

thay,

Do đó công thức thay thế cho máy tính xác suất kết hợp:

Nếu bạn cần tôi mở rộng về điều này, vui lòng để lại nhận xét.

Answer 4

Tôi không mạnh về toán học nên tôi không thể nhận xét về các đơn giản hóa có thể có đối với công thức có thể loại bỏ hoặc giảm sự cố của bạn. Tuy nhiên, tôi làm quen với những hạn chế độ chính xác của các loại đôi dài và nhận thức được một số thư viện chính xác toán học tùy ý và mở rộng cho C. Kiểm tra:

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

Answer 5

Hãy thử tính toán nghịch đảo 1/p . Điều đó cung cấp cho bạn phương trình của biểu mẫu 1 + 1/(1-p1) * (1-p2) ...

Nếu sau đó bạn đếm số lần xuất hiện của mỗi xác suất - có vẻ như bạn có một số lượng nhỏ các giá trị tái diễn - bạn có thể sử dụng hàm pow() - pow (1-p, occurrences_of_p) * pow (1-q, occurrences_of_q) - và tránh làm tròn riêng lẻ với mỗi phép nhân.

Answer 6

Dưới đây là một thủ thuật:

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) 

Vì vậy, về cơ bản, bạn sẽ có được một sản phẩm của con số khá lớn (giữa 0 và, cho p_i = 0.01, 99). Ý tưởng là, không phải nhân số tấn các số nhỏ với nhau, để có được, tốt, 0, nhưng để làm cho thương của hai số nhỏ. Ví dụ: nếu n = 1000000 and p_i = 0.5 for all i, phương pháp trên sẽ cung cấp cho bạn 0/(0+0) là NaN, trong khi phương pháp được đề xuất sẽ cung cấp cho bạn 1/(1+1*...1), là 0.5.

Bạn có thể có được kết quả tốt hơn, khi tất cả p_i đều được sắp xếp và bạn ghép chúng lên để phản đối (hãy giả sử p_1 < ... < p_n), sau đó công thức sau sẽ nhận được độ chính xác tốt hơn:

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

cách mà bạn chia các tử số lớn (nhỏ p_i) với các mẫu số lớn (lớn p_(n+1-i)), và các tử số nhỏ có mẫu số nhỏ.

chỉnh sửa: MSalter đề xuất tối ưu hóa hữu ích hơn nữa trong câu trả lời của mình. Sử dụng nó, công thức đọc như sau:

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)