Проблема с точной работой с плавающей запятой в C

Для одного из моих курсовых проектов я начал внедрять «Naive Bayesian classifier» в C. Мой проект – реализовать приложение classификатора документов (особенно Spam) с использованием огромных данных обучения.

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

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

ЗАЯВЛЕНИЕ О ПРОБЛЕМЕ: Алгоритм включает в себя принятие каждого слова в документе и вычисление вероятности его спам-слова. Если p1, p2 p3 …. pn – вероятности слова-1, 2, 3 … n. Вероятность того, что doc является спамом или нет, вычисляется с использованием

alt text

Здесь значение вероятности может быть очень легко около 0,01. Поэтому, даже если я использую datatype «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, двойные и даже длинные двойные типы данных, но все еще та же проблема.

Следовательно, скажем, в документе на 100 тыс. Слов, который я анализирую, если только 162 слова имеют 1% вероятности спама, а оставшиеся 99838 являются явно спам-словами, то все же мое приложение скажет это как не спам-документ из-за ошибки Precision (поскольку числитель легко переходит к ZERO) !!!.

Это первый раз, когда я сталкиваюсь с такой проблемой. Итак, как именно эта проблема должна решаться?

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

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

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

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

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

    Я решил сделать математику,

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

    проблема

    Я немного модифицирую его:

    введите описание изображения здесь

    Принимая журналы с обеих сторон:

    введите описание изображения здесь

    Позволять,

    введите описание изображения здесь

    Подставляя,

    введите описание изображения здесь

    Следовательно, альтернативная формула для вычисления комбинированной вероятности:

    введите описание изображения здесь

    Если вам нужно, чтобы я расширил это, пожалуйста, оставьте комментарий.

    Вот трюк:

     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) 

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

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

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

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

    или же

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

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

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

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