Наивный байесовский классификатор с плавающей точкой

Question

Умножение большого количества вероятностей в наивных байесовских алгоритмах может привести к недостаточному вычислению с плавающей точкой.

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

Предполагая, что все вероятности находятся в разумном диапазоне, скажем, [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/infinities/zeroes/subnormals.

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

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

Answer 2

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

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

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

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