eficientemente que resumen las cantidades de registro

Trabajando en C++, me gustaría encontrar la suma de algunas cantidades, y luego tomar el logaritmo de la suma:eficientemente que resumen las cantidades de registro

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

Sin embargo, no tengo las cantidades a sí mismos, lo sólo tienen sus valores log'd:

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

¿hay alguna forma eficiente de obtener el registro de la suma de los años a_i? Me gustaría evitar

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

si es posible - exp se convierte en un cuello de botella ya que el cálculo se realiza muchas veces.

Fuente

2011-02-04 Mike B

Oye, eso es una [pregunta matemática] (http://jblevins.org/notes/log-sum- exp) disfrazado! –

Lástima que no esté buscando el registro (a_1 * ... * a_n) - ¡podría simplemente sumar los valores de registro que tiene! –

¿Cuáles son esas cantidades? ¿Hay alguna relación entre ellos? –

¿Qué tan grande es n?

Esta cantidad se conoce como log-sum-exp y Lieven Vandenberghe habla de ello en la página 72 de su book. También tiene un optimization package que usa esta operación, y desde un breve vistazo, parece que no hace nada especial allí, simplemente expone y agrega. Quizás la exponenciación no sea un cuello de botella serio cuando n es lo suficientemente pequeño como para que el vector encaje en la memoria.

Esta operación a menudo aparece en el modelado y el cuello de botella es la gran cantidad de términos. La magnitud de n = 2^100 es común, donde los términos están representados implícitamente. En tales casos, hay varios trucos para aproximar esta cantidad basándose en la convexidad de log-sum-exp. El truco más simple: log (s) aproximado (s) como máximo (l1, l2, ..., ln)

Fuente

2011-02-05 01:50:55

No sé de ninguna manera, porque, en general, no hay manera de calcular

e ^{x + e}^y

usando la suma y sólo uno exponenciación, que es equivalente a lo que estás preguntando.

Como se mencionó en el comentario de Frédéric Hamidi anteriormente, incluso si lo hace sumar los exponentes, tiene otro problema que preocuparse: desbordamiento. El link he gave da una muy buena solución (siguiente código Fortran copiado de ese vínculo):

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

Fuente

2011-02-04 23:14:17

podría utilizar la siguiente identidad:

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

Fuente

2011-02-04 23:19:26 mocj

Eso es lo que utiliza el enlace de Frédéric Hamidi para evitar el desbordamiento; pero, ¿cómo ayuda esto con más de dos variables? –

@BlueRaja, no ayuda, si no me equivoco, todavía tiene que calcular exponentes para cada término. Para decirlo de forma romántica, el interlocutor quiere predecir el futuro cruzando las curvas de log() ed, por lo que tiene que pagar el precio y calcular todos los exponentes (y tenga cuidado con el desbordamiento/subdesbordamiento). –

En lugar de necesitar n llamadas a exp(), ahora necesita n/2 llamadas a exp() y n/2 a log(). Log() debe ser rápido debido a las instrucciones nativas de la CPU. exp() ~ no tanto ... – mocj

No es muy elegante, pero puede probar con el siguiendo.

Obtener lg a_i de log a_i (dividir por log 2).
Vamos lg a_i = k + q donde k es entero y q es real y 0 >= q >= 1
Obtener a_i con 2 ^kpow(2,q) (uso desplazamiento de bits para 2 ^k = 1 << k).
Puede acelerar pow(2,q) con tablas de cálculo previo de precisión limitada para [0,1]

Así que la idea es aprovechar una función rápida de potencias de 2. ¡Espero eso ayude!

Fuente

2011-02-04 23:34:11 Jacob

Si s_k: = sum(a_1 + ... + a_k) entonces s_ {k + 1} == s_k + f(l_{k+1} - s_k), donde

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

Esta función f probablemente se puede calcular con una serie de Taylor o similar con una velocidad comparable a exp, y posiblemente incluso en línea.

Eso solo ahorra aproximadamente dos funciones matemáticas, pero podría ser un punto de partida útil.

Fuente

2011-02-05 01:10:38 aschepler

eficientemente que resumen las cantidades de registro

Respuesta

Cuestiones relacionadas