Эффективное суммирование журналов

Question

Работая в C ++, я хотел бы найти сумму некоторых величин, а затем взять журнал суммы:

log(a_1 + a_2 + a_3 + ... + a_n)

Однако у меня нет самих величин, у меня есть только их лог-значения:

l_1 = log(a_1), l_2 = log(a_2), ... , l_n = log(a_n)

Есть ли какой-нибудь эффективный способ получить в логе сумму a_i? Я бы хотел избежать

log(s) = log(exp(l_1) + exp(l_2) + ... + exp(l_n))

если возможно - exp становится узким местом, так как вычисления выполняются много раз.

Answer 1

Насколько велика n?

Это количество известно как log-sum-exp, и Ливен Ванденберг рассказывает об этом на странице 72 своей книги . У него также есть пакет оптимизации , который использует эту операцию, и из краткого обзора кажется, что он не делает там ничего особенного, только возводит в степень и добавляет. Возможно, возведение в степень не является серьезным узким местом, когда n достаточно мало, чтобы вектор поместился в памяти.

Эта операция часто возникает при моделировании, и узким местом является огромное количество терминов. Величина n = 2 ^ 100 является общей, где члены представлены неявно. В таких случаях существуют разные приемы аппроксимации этой величины, основанные на выпуклости log-sum-exp. Самый простой трюк - приблизительный лог (ы) как max (l1, l2, ...., ln)

Answer 2

Я не знаю, потому что, как правило, нет способа вычислить

e ^x + e ^y

с использованием сложения и только одного возведения в степень, что эквивалентно тому, что вы спрашиваете.

---

Как уже упоминалось в комментарии Фредерика Хамиди выше, даже еслиВы суммируете показатели, у вас есть еще одна проблема: переполнение.Ссылка , которую он дал , дает довольно хорошее решение (после кода Фортрана, скопированного из этой ссылки) :

function log_sum_exp(v) result(e)
  real, dimension(:), intent(in) :: v   ! Input vector
  real                           :: e   ! Result is log(sum(exp(v)))
  real                           :: c   ! Shift constant

  ! Choose c to be the element of v that is largest in absolute value.
  if ( maxval(abs(v)) > maxval(v) ) then
     c = minval(v)
  else
     c = maxval(v)
  end if

  e = log(sum(exp(v-c))) + c
end function log_sum_exp

Answer 3

Если s_k: = sum(a_1 + ... + a_k), то s_ {k + 1} == s_k + f(l_{k+1} - s_k), где

f(x) := log(1+exp(x))

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

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

Answer 4

Это не очень элегантно, но вы можете попробовать следующее.

• Получить lg a_i из log a_i (разделить на log 2).
• Пусть lg a_i = k + q, где k - целое число иq является действительным и 0 >= q >= 1
• Получите a_i с 2 ^k pow(2,q) (используйте битовое смещение для 2 ^k = 1 << k).
• Вы можете ускорить pow(2,q) с помощью предварительно вычисленных таблиц ограниченной точности для [0,1]

Таким образом, вся идея состоит в том, чтобы использовать быструю функцию степени 2.Надеюсь, это поможет!

Answer 5

Вы можете использовать следующую личность:

log( a + b ) = log(a) + log( 1 + (b/a) )