¿Por qué es más rápido agregar probabilidades de registro que multiplicar probabilidades?

Para enmarcar la pregunta, en informática a menudo queremos calcular el producto de varias probabilidades:

P(A,B,C) = P(A) * P(B) * P(C)

El enfoque más simple es simplemente multiplicar estos números, y eso es lo que iba a hacer. Sin embargo, mi jefe dijo que es mejor agregar el registro de las probabilidades:

log(P(A,B,C)) = log(P(A)) + log(P(B)) + log(P(C))

Esto da la probabilidad de registro, pero podemos obtener la probabilidad después si es necesario:

P(A,B,C) = e^log(P(A,B,C))

La adición de registros se considera mejor por dos razones:

Evita el "desbordamiento" por el cual el producto de las probabilidades es tan pequeño que se redondea a cero. Esto a menudo puede ser un riesgo ya que las probabilidades son a menudo muy pequeñas.
Es más rápido porque muchas arquitecturas de computadora pueden realizar la suma más rápidamente que la multiplicación.

Mi pregunta es sobre el segundo punto. Así es como lo he visto descrito, ¡pero no tiene en cuenta el costo adicional de obtener el registro! Deberíamos comparar "costo de registro + costo de adición" con "costo de multiplicación". ¿Sigue siendo más pequeño después de tener eso en cuenta?

Además, la página de Wikipedia ( probabilidad de registro ) es confusa a este respecto, afirmando que "la conversión al formulario de registro es costosa, pero solo se incurre una vez". No entiendo esto, porque creo que necesitaría tomar el registro de cada término de forma independiente antes de agregar. ¿Qué me estoy perdiendo?

Finalmente, la justificación de que "las computadoras realizan la suma más rápido que la multiplicación" es algo vaga. ¿Es eso específico del conjunto de instrucciones x86, o es un rasgo más fundamental de las arquitecturas de procesador?

algorithm-analysis probability-theory Stephen
fuente

El primer beneficio (evitar el desbordamiento) a menudo es mucho más importante que la ganancia de rendimiento, por lo que incluso si no fuera más rápido, seguiríamos usando probabilidades de registro.

Para ampliar lo que dijo @DW, hay un "truco de log-sum-exp" similar que se usa específicamente para abordar el desbordamiento, sin tener en cuenta el rendimiento en absoluto. De hecho, ¡esta era la primera vez que veía a alguien considerar los logaritmos como una técnica para mejorar el rendimiento!

Mehrdad

Respuestas:

Además, la página de Wikipedia ( https://en.wikipedia.org/wiki/Log_probability ) es confusa a este respecto, afirmando que "La conversión al formulario de registro es costosa, pero solo se incurre una vez". No entiendo esto, porque creo que necesitaría tomar el registro de cada término de forma independiente antes de agregar. ¿Qué me estoy perdiendo?

Si solo desea calcular una vez, entonces tiene razón. Tendrás que calcular logaritmos y adiciones, mientras que el método ingenuo requiere multiplicaciones. $P(A_1)\ldots P(A_n)$ $n$ $n-1$ $n-1$

Sin embargo, es muy común que desee responder consultas del formulario:

$\prod_{i \in I} P(A_i)$ $I$ $\{1, \ldots n\}$

$\log P(A_i)$ $|I|$

Finalmente, la justificación de que "las computadoras realizan la suma más rápido que la multiplicación" es algo vaga. ¿Es eso específico del conjunto de instrucciones x86, o es un rasgo más fundamental de las arquitecturas de procesador?

$a+b$ $a$ $b$ $a\times b$

$2$

Sin embargo, esta es una declaración razonable en todas las arquitecturas informáticas comunes: la multiplicación en números de punto flotante será más lenta que la suma.

md5
fuente

P (A_{i})

$P(A_i)$

¿Qué pasa con la exp final ()? ¿No es lento?

Mehrdad

Θ (M (n) \log n)

$\Theta(M(n)\log n)$

M (n)

$M(n)$

Θ (n M (n) \log n + n \sum_{q \in Q} | I_{q} |)

$\Theta(nM(n)\log n+n\sum_{q\in Q}|I_q|)$

Q

$Q$ es el conjunto de consultas).

md5

\exp

$\exp$

n

$n$

(0, 1)

$(0,1)$

\log

$\log$

10

$10$

¿Es la suma aún más rápida que la multiplicación si usa flotadores IEEE, lo que ciertamente lo hará en este caso? Los cpus modernos son bastante buenos para multiplicar números, mientras que la adición de flotador tiene un par de pasos que no se pueden ejecutar simultáneamente: alinee las mantisas (desplace a la izquierda según el resultado de la resta), luego agréguelas, luego normalice (lo que puede desencadenar tanto el desbordamiento como desbordamiento, yay). En el circuito son muchos dados, en microcódigo cada paso cuesta un ciclo o pocos.

John Dvorak

$N$ $p_1,...p_N$ $p_i$

$N$

$O(n)$ $n$ $O(n^2)$

Por cierto, esta idea es similar a la multiplicación modular de Montgomery, donde las multiplicaciones se realizan en la forma de Montgomery, que es bastante más rápida que la multiplicación habitual y luego la reducción.

fade2black
fuente

-1 La multiplicación no toma tiempo cuadrático ...

Mehrdad

@Mehrdad, espero que hayas aprendido la multiplicación escolar de dos números. Ese algoritmo todavía se usa ampliamente en chips de computadora. Mire aquí. Lo que quiere decir es que los algoritmos de nivel de software son aún peores que el tiempo lineal. ¿Son estos algoritmos de multiplicación ampliamente utilizados como en el circuito de multiplicación?

fade2black

en.wikipedia.org/wiki/Carry-save_adder#The_basic_concept

Mehrdad

Sin embargo, el espíritu de la respuesta sigue siendo correcto, ¿verdad? Si ninguno de los algoritmos de multiplicación va a coincidir con el tiempo lineal de la suma?

Stephen

@Stephen, de hecho, la pregunta no era sobre cuál es la mejor complejidad exacta del algoritmo de multiplicación. Podría proporcionar información adicional sobre este tema si los comentaristas lo requieren. Creo que una larga discusión sobre eso estaría fuera de tema aquí. )))

fade2black