Проблема с точностью операции с плавающей точкой в ​​C

Question

Для одного из моих курсовых проектов я начал реализацию «Наивного байесовского классификатора» на C. Мой проект заключается в реализации приложения классификатора документов (особенно спама) с использованием огромных обучающих данных.

Теперь у меня проблема с реализацией алгоритма из-за ограничений в типе данных Си.

(алгоритм, который я использую, приведен здесь, http://en.wikipedia.org/wiki/Bayesian_spam_filtering)

ПОСТАНОВКА ЗАДАЧИ: Алгоритм включает взятие каждого слова в документе и вычисление вероятности того, что это слово является спамом. Если p1, p2 p3 .... pn - вероятности слова -1, 2, 3 ... n. Вероятность того, что документ является спамом или нет, рассчитывается с использованием

Здесь значение вероятности может быть очень легко около 0,01. Таким образом, даже если я использую тип данных "double", мой расчет пойдет на бросок. Чтобы подтвердить это, я написал пример кода, приведенного ниже.

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

Я пробовал Float, double и даже long double типы данных, но все еще та же проблема.

Следовательно, скажем, в анализируемом документе из 100 тыс. Слов, если только 162 слова имеют вероятность спама в 1%, а оставшиеся 99838 являются явно спам-словами, то мое приложение все равно будет называть его «Не спам-документ» из-за ошибки точности (как нумератор легко уходит в НОЛЬ) !!!.

Я впервые сталкиваюсь с такой проблемой. Так как именно решить эту проблему?

Answer 1

Это часто случается в машинном обучении. AFAIK, ты ничего не можешь сделать с потерей точности. Чтобы обойти это, мы используем функцию log и преобразуем деления и умножения в вычитания и сложения, соответственно

Так что я решил сделать математику,

Исходное уравнение:

Я немного изменяю это:

Принимая бревна с обеих сторон:

Пусть

Подставив

Отсюда и альтернативная формула для вычисления суммарной вероятности:

Если вам понадобится дополнительная информация, пожалуйста, оставьте комментарий.

Answer 2

Вот хитрость:

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)

Таким образом, в основном вы получите произведение довольно больших чисел (от 0 до p_i = 0.01, 99). Идея состоит не в том, чтобы умножить тонны небольших чисел друг на друга, чтобы получить, ну, в общем, 0, а в том, чтобы получить частное от двух небольших чисел. Например, если n = 1000000 and p_i = 0.5 for all i, вышеуказанный метод даст вам 0/(0+0), что составляет NaN, тогда как предложенный метод даст вам 1/(1+1*...1), что составляет 0.5.

Вы можете получить еще лучшие результаты, когда все p_i отсортированы и вы объедините их в обратном порядке (предположим, p_1 < ... < p_n), тогда следующая формула получит еще большую точность:

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

таким образом вы делите большие числители (маленькие p_i) с большими знаменателями (большие p_(n+1-i)) и маленькие числители с маленькими знаменателями.

edit: MSalter предложил полезную дополнительную оптимизацию в своем ответе. Используя его, формула гласит:

  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)

Answer 3

Ваша проблема вызвана тем, что вы собираете слишком много терминов без учета их размера. Одно из решений - взять логарифмы. Другой способ сортировать ваши индивидуальные условия. Во-первых, давайте перепишем уравнение как 1/p = 1 + ∏((1-p_i)/p_i). Теперь ваша проблема в том, что некоторые термины маленькие, а другие большие. Если у вас в строке слишком много маленьких терминов, вы будете недополучать, а слишком много больших терминов переполняют промежуточный результат.

Итак, не ставьте слишком много одинакового порядка подряд. Сортировать условия (1-p_i)/p_i. В результате первый будет самым маленьким, последний - самым большим. Теперь, если вы умножите их сразу, у вас все равно будет недостаток. Но порядок расчета не имеет значения. Используйте два итератора в вашу временную коллекцию. Один начинается с начала (т. Е. (1-p_0)/p_0), другой - с конца (т. Е. (1-p_n)/p_n), а ваш промежуточный результат начинается с 1.0. Теперь, когда ваш промежуточный результат> = 1.0, вы берете термин с фронта, а когда ваш промежуточный результат <1.0, вы берете результат сзади. </p>

В результате, если вы берете термины, промежуточный результат будет колебаться около 1,0. Он будет расти или падать только тогда, когда у вас закончатся маленькие или большие условия. Но это нормально. В этот момент вы использовали крайности на обоих концах, поэтому промежуточный результат будет медленно приближаться к конечному результату.

Конечно, существует реальная возможность переполнения. Если входные данные вряд ли будут спамом (p = 1E-1000), то 1/p будет переполнен, потому что ∏((1-p_i)/p_i) переполнен. Но поскольку термины отсортированы, мы знаем, что промежуточный результат будет переполнен только , если ∏((1-p_i)/p_i) переполнится. Таким образом, если промежуточный результат переполняется, нет последующей потери точности.

Answer 4

Попробуйте вычислить обратное значение 1 / p. Это дает вам уравнение вида 1 + 1 / (1-p1) * (1-p2) ...

Если затем подсчитать возникновение каждой вероятности - похоже, у вас есть небольшое количество повторяющихся значений - вы можете использовать функцию pow () - pow (1-p, occurences_of_p) * pow (1 -q, emersions_of_q) - и избегать отдельного округления при каждом умножении.

Answer 5

Вы можете использовать вероятность в процентах или промилле:

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

или

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

или используйте другой коэффициент

Answer 6

Я не силен в математике, поэтому я не могу комментировать возможные упрощения формулы, которые могут устранить или уменьшить вашу проблему. Однако я знаком с ограничениями точности длинных двойных типов и знаю несколько математических библиотек с произвольной и расширенной точностью для C. Проверьте:

http://www.nongnu.org/hpalib/ а также http://www.tc.umn.edu/~ringx004/mapm-main.html