Наивная байесовская классификация с плавающей точкой Underflow

Question

Умножение множества вероятностей в Naïve Bayes может привести к потоку с плавающей запятой.

P(x_1,….,x_n│c) = P(x_1│c).P(x_2│c).P(x_3│c)… … P(x_n |c) 

Вместо того чтобы использовать приведенную выше формулу (результат с плавающей точкой в ​​опустошении), это более осуществимо/лучше использовать формулы, приведенные ниже? Или он обрезает информацию?

log(xy) = log(x) + log(y) 

Answer 1

До того момента, когда сгущенного или переполнение происходит с плавающей точкой умножения является лучшим из себя операций с плавающей запятой. Кроме того, в вашей формуле, как только достигнут нижний уровень, известно, что конечное значение невелико, поскольку необработанные факторы меньше 1,0 и могут только способствовать уменьшению конечного результата.

Использование логарифма только уменьшает точность в целом, сначала из-за самого логарифма и во-вторых, потому что добавление чисел с разной величиной с плавающей запятой составляет не хорошо.

Если вы не заботитесь о разнице между вероятностью 2 ^-1024 и вероятностью нуля для какой-либо причины, что ваш вопрос не сказать, я не понимаю, почему вы хотели бы изменить хорошо себя умножения в первая формула в опасные дополнения во втором.

NB: у вас должно быть что-то вроде 20 факторов, каждый порядка 2 ^-50 для нижестоящего бинарного формата IEEE 754. Если это то, что вы ожидаете и которое хотите обрабатывать с точностью, вы можете подумать о переходе на 80-битный формат с двойным расширением, если ваш компилятор делает этот тип доступным (например, long double, если вы используете C), или до MPFR, который, как я полагаю, использует полное слово для представления экспоненты.

Answer 2

Предполагая, что все вероятности в разумных пределах, скажем, [2^{- 63}, 2^{63}], вы можете накапливать продукт, как это:

double prod(double *d, int n, int64_t *expo) { 
    *expo = 0; 
    double ans = 1; 
    for (int i = 0; i < n; i++) { 
    ans *= d[i]; 
    if (!(i % 16)) { 
     int foo = 0; 
     ans = frexp(ans, &foo); 
     expo += foo; 
    } 
    } 
} 

Продукт затем в пределах n/2 ulp возвращаемого значения времени 2^{*expo}. Этот код достаточно прост для векторизации, и также довольно легко написать альтернативу, более быструю, frexp для этого особого случая, который просто выполняет бит-скрининг и игнорирует NaNs/бесконечности/нули/субнормальные значения.

Если ваша платформа поддерживает захват арифметики с плавающей запятой, и ваш ввод, как известно, лежит в разумном, но неизвестном диапазоне, вы можете адаптировать шаг с минимальным воздействием на большие n, добавив обработчики ловушек для переполнения и переполнения , Это, вероятно, проще всего сделать, если вы напишете как процедуру продукта, так и обработчик ловушки на ассемблере вашей платформы.

Если вместо этого вы добавляете логарифмы, вы теряете значительную точность, сначала беря логарифмы, а во-вторых, суммируя их, что вам может или не нужно. Хуже то, что вы также теряете значительное количество скорости, вычисляя столько логарифмов.