Por que adicionar probabilidades de log é mais rápido que multiplicar probabilidades?

Para enquadrar a questão, na ciência da computação, muitas vezes queremos calcular o produto de várias probabilidades:

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

A abordagem mais simples é simplesmente multiplicar esses números, e era isso que eu ia fazer. No entanto, meu chefe disse que é melhor adicionar o log de probabilidades:

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

Isso fornece a probabilidade do log, mas podemos obter a probabilidade posteriormente, se necessário:

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

A adição de log é considerada melhor por dois motivos:

Impede o "underflow", pelo qual o produto das probabilidades é tão pequeno que é arredondado para zero. Isso geralmente pode ser um risco, pois as probabilidades são muitas vezes muito pequenas.
É mais rápido porque muitas arquiteturas de computadores podem realizar acréscimos mais rapidamente que multiplicação.

Minha pergunta é sobre o segundo ponto. É assim que eu o descrevi, mas não leva em conta o custo adicional de obter o log! Deveríamos comparar "custo de log + custo de adição" com "custo de multiplicação". Ainda é menor depois de levar isso em conta?

Além disso, a página da Wikipedia ( probabilidade de log ) é confusa a esse respeito, afirmando "A conversão para o formulário de log é cara, mas é incorrida apenas uma vez". Eu não entendo isso, porque acho que você precisaria tomar o log de todos os termos independentemente antes de adicioná-lo. o que estou perdendo?

Finalmente, a justificativa de que "os computadores executam adição mais rápido que a multiplicação" é meio vaga. Isso é específico para o conjunto de instruções x86 ou é uma característica mais fundamental das arquiteturas de processador?

algorithm-analysis probability-theory Stephen
fonte

O primeiro benefício (evitar o estouro) geralmente é muito mais importante que o ganho de desempenho, portanto, mesmo que não fosse mais rápido, ainda usaríamos probabilidades de log.

Para expandir o que o @DW disse, existe um "truque de soma e exp de log" usado especificamente para lidar com o fluxo insuficiente, sem nenhuma consideração ao desempenho. De fato, foi a primeira vez que vi alguém considerar o logaritmo como uma técnica de melhoria de desempenho!

Mehrdad

Respostas:

Além disso, a página da Wikipedia ( https://en.wikipedia.org/wiki/Log_probability ) é confusa a esse respeito, afirmando "A conversão para o formulário de log é cara, mas é incorrida apenas uma vez". Eu não entendo isso, porque acho que você precisaria tomar o log de todos os termos independentemente antes de adicioná-lo. o que estou perdendo?

$P(A_1)\ldots P(A_n)$ $n$ $n-1$ $n-1$

No entanto, é muito comum que você queira responder a consultas do formulário:

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

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

Finalmente, a justificativa de que "os computadores executam adição mais rápido que a multiplicação" é meio vaga. Isso é específico para o conjunto de instruções x86 ou é uma característica mais fundamental das arquiteturas de processador?

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

$2$

No entanto, esta é uma afirmação razoável em todas as arquiteturas comuns de computadores: a multiplicação em números de ponto flutuante será mais lenta que a adição.

md5
fonte

P (A_{i})

$P(A_i)$

E a exp () final? Isso não é 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$ é o conjunto de consultas).

Md5

\exp

$\exp$

n

$n$

(0, 1)

$(0,1)$

\log

$\log$

10

$10$

A adição ainda é mais rápida que a multiplicação se você usar flutuadores IEEE - o que certamente você fará neste caso? As cpus modernas são muito boas em multiplicar números, enquanto a adição de float tem algumas etapas que não podem ser executadas simultaneamente - alinhe mantissas (alterne para a esquerda com base no resultado da subtração), adicione-as e, em seguida, normalize-as (o que pode desencadear subfluxo e estouro). No circuito, são muitas as matrizes, no microcódigo, cada etapa custa um ciclo ou poucos.

John Dvorak

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

$N$

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

A propósito, essa idéia é semelhante à multiplicação modular de Montgomery, onde as multiplicações são realizadas na forma de Montgomery, que é bem mais rápida que a multiplicação usual e depois a redução.

fade2black
fonte

-1 A multiplicação não leva tempo quadrático ...

Mehrdad 24/06

@ Mehrdad, espero que você tenha aprendido a multiplicação escolar de dois números. Esse algoritmo ainda é amplamente usado em chips de computador, por favor, veja aqui O que você quer dizer com algoritmos em nível de software que são ainda piores que o tempo linear. Esses algoritmos de multiplicação são amplamente utilizados como no circuito de multiplicação?

Fade2black 24/06

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

Mehrdad

O espírito da resposta ainda está correto, certo? Se nenhum dos algoritmos de multiplicação corresponderá ao tempo linear de adição?

Stephen

@ Stephen, na verdade a questão não era sobre qual é a melhor e exata complexidade do algoritmo de multiplicação. Eu poderia fornecer informações adicionais sobre este assunto, se necessário. Eu acho que uma longa discussão sobre isso seria fora de tópico aqui. )))

fade2black