Pregunta ¿Cómo lidiar con el subdesbordamiento en la informática científica?


Estoy trabajando en modelos probabilísticos, y al hacer inferencias sobre esos modelos, las probabilidades estimadas pueden volverse muy pequeñas. Para evitar subdesbordamientos, actualmente estoy trabajando en el dominio de registro (almaceno el registro de las probabilidades). Multiplicar probabilidades es equivalente a una suma, y ​​la suma se hace usando la fórmula:

log(exp(a) + exp(b)) = log(exp(a - m) + exp(b - m)) + m

dónde m = max(a, b).

Yo uso algunas matrices muy grandes, y tengo que tomar la exponencial de las matrices para calcular las multiplicaciones de matrices-vectores. Este paso es bastante caro, y me preguntaba si existen otros métodos para tratar el subdesbordamiento, cuando se trabaja con probabilidades.

Editar: por razones de eficiencia, busco una solución que use tipos primitivos y no objetos que almacenen una representación de precisión de números reales.

Editar 2: Estoy buscando una solución más rápida que el truco del dominio de registro, no una solución más precisa. Estoy contento con la precisión que recibo actualmente, pero necesito un método más rápido. Particularmente, las sumas suceden durante las multiplicaciones de matrices-vectores, y me gustaría poder usar métodos BLAS eficientes.

Solución: después de una discusión con Jonathan Dursi, decidí factorizar cada matriz y vector por su elemento más grande, y almacenar ese factor en el dominio de registro. Las multiplicaciones son directas. Antes de las adiciones, tengo que factorizar una de las matrices / vectores agregados por la relación de los dos factores. Actualizo el factor cada diez operaciones.


10
2018-02-17 23:06


origen


Respuestas:


Este problema ha surgido recientemente en el sitio de intercambio de pila de ciencia computacional también, y aunque existe la preocupación inmediata de que haya desbordamiento, los problemas son más o menos lo mismo.

Transformar en espacio de registro es ciertamente un enfoque razonable. Independientemente del espacio en el que se encuentre, para hacer una gran cantidad de sumas correctamente, hay un par de métodos que puede usar para mejorar la precisión de sus sumas. Enfoques de suma compensados, más famoso Kahan suma, mantenga una suma y lo que efectivamente es un "resto"; le da algunas de las ventajas de usar aritmeitica de mayor precisión sin todo el costo (y solo con tipos primitivos). El término restante también le da una indicación de qué tan bien lo está haciendo.

Además de mejorar la mecánica real de su adición, cambiar el orden de cómo agrega sus términos puede marcar una gran diferencia. Clasificar los términos para que esté sumando de menor a mayor puede ayudar, ya que entonces ya no agrega términos tan frecuentemente que son muy diferentes (lo que puede causar problemas importantes de redondeo); en algunos casos, haciendo registro2 N repetidas sumas por parejas también puede ser una mejora sobre simplemente hacer la suma lineal directa, dependiendo de cómo se vean sus términos.

La utilidad de todos estos enfoques depende mucho de las propiedades de sus datos. Las bibliotecas matemáticas de precisión arbitraria, aunque son enormemente caras en el tiempo de cálculo (y posiblemente de memoria), tienen la ventaja de ser una solución bastante general.


9
2018-02-18 15:38



Me encontré con un problema similar hace años. La solución fue desarrollar una aproximación de log (1 + exp (-x)). El rango de la aproximación no necesita ser tan grande (x de 0 a 40 será más que suficiente), y al menos en mi caso la precisión tampoco tenía que ser particularmente alta.

En su caso, parece que necesita calcular el registro (1 + exp (-x1) + exp (-x2) + ...). Deseche esos valores negativos grandes. Por ejemplo, supongamos que a, byc son tres probabilidades de registro, con 0> a> b> c. Puede ignorar c si a-c> 38. No va a contribuir en absoluto a su probabilidad de registro conjunta, al menos no si está trabajando con dobles.


4
2018-02-18 16:52



Opción 1:  Commons Math - The Apache Commons Mathematics Library

Commons Math es una biblioteca de componentes livianos, autónomos de matemáticas y estadísticas que abordan los problemas más comunes que no   disponible en el lenguaje de programación Java o Commons Lang.

Nota: La API protege a los constructores para forzar un patrón de fábrica al nombrar el DfpField de fábrica (en lugar del DfpFac o DfpFactory algo más intuitivo). Entonces debes usar

new DfpField(numberOfDigits).newDfp(myNormalNumber)

para instanciar un Dfp, entonces puede llamar .multiply o lo que sea en esto. Pensé en mencionar esto porque es un poco confuso.

Opcion 2:  Biblioteca Científica GNU o Boost C ++ Libraries. En estos casos debes usar JNI para llamar a estas bibliotecas nativas

Opción 3: Si tiene la libertad de usar otros programas y / o idiomas, podría considerar el uso de programas / idiomas para cálculos numéricos tales como Octava, Scilaby similar.

Opción 4:  BigDecimal de Java.


4
2018-02-17 23:35



En lugar de almacenar valores en forma logarítmica, creo que probablemente sería mejor usar el mismo concepto que doubles, a saber, representación en coma flotante. Por ejemplo, puede almacenar cada valor como dos longs, uno para signo y mantisa y uno para el exponente. (Real el punto flotante tiene un diseño cuidadosamente afinado para admitir muchos casos extremos y evitar desperdiciar un solo bit; pero probablemente no tenga que preocuparse tanto por ninguno de ellos, y puede concentrarse en diseñarlo de una manera que sea fácil de implementar).


1
2018-02-18 00:39



No entiendo por qué esto funciona, pero esta fórmula parece funcionar y es más simple:

c = a + log(1 + exp(b - a))

Dónde c = log(exp(a)+exp(b))


0
2017-09-19 21:55