Pourquoi est-il plus rapide d'ajouter des probabilités de log que de multiplier des probabilités?

Pour formuler la question, en informatique, nous voulons souvent calculer le produit de plusieurs probabilités:

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

L'approche la plus simple consiste simplement à multiplier ces nombres, et c'est ce que j'allais faire. Cependant, mon patron a dit qu'il valait mieux ajouter le journal des probabilités:

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

Cela donne la probabilité logarithmique, mais nous pouvons obtenir la probabilité par la suite si nécessaire:

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

L'ajout de journaux est considéré comme meilleur pour deux raisons:

Il empêche le "sous-dépassement" par lequel le produit des probabilités est si petit qu'il est arrondi à zéro. Cela peut souvent être un risque car les probabilités sont souvent très faibles.
C'est plus rapide car de nombreuses architectures informatiques peuvent effectuer l'addition plus rapidement que la multiplication.

Ma question porte sur le deuxième point. C'est ainsi que je l'ai vu décrit, mais il ne prend pas en compte le coût supplémentaire d'obtention du journal! Nous devrions comparer le "coût du journal + le coût de l'addition" au "coût de la multiplication". Est-il encore plus petit après en avoir tenu compte?

De plus, la page Wikipédia ( probabilité de journalisation) prête à confusion à cet égard, déclarant que "la conversion sous forme de journal est coûteuse, mais n'est engagée qu'une seule fois". Je ne comprends pas cela, car je pense que vous auriez besoin de prendre le journal de chaque terme indépendamment avant d'ajouter. Qu'est-ce que je rate?

Enfin, la justification selon laquelle "les ordinateurs effectuent l'addition plus rapidement que la multiplication" est assez vague. Est-ce spécifique au jeu d'instructions x86, ou s'agit-il d'un trait plus fondamental des architectures de processeur?

algorithm-analysis probability-theory Stephen
la source

Le premier avantage (éviter les débordements) est souvent beaucoup plus important que le gain de performances, donc même s'il n'était pas plus rapide, nous utiliserions toujours les probabilités de journalisation.

Pour développer ce que @DW a dit, il existe une "astuce log-sum-exp" similaire utilisée spécifiquement pour remédier au sous-dépassement, sans aucune considération pour les performances. En fait, c'était la première fois que je voyais quelqu'un considérer les logarithmes comme une technique d'amélioration des performances!

Mehrdad

Réponses:

De plus, la page Wikipédia ( https://en.wikipedia.org/wiki/Log_probability ) prête à confusion à cet égard, indiquant que «la conversion en forme de journal est coûteuse, mais n'est engagée qu'une seule fois». Je ne comprends pas cela, car je pense que vous auriez besoin de prendre le journal de chaque terme indépendamment avant d'ajouter. Qu'est-ce que je rate?

Si vous voulez juste calculer une fois, alors vous avez raison. Vous devrez calculer logarithmes et additions, alors que la méthode naïve nécessite multiplications. $P(A_1)\ldots P(A_n)$ $n$ $n-1$ $n-1$

Cependant, il est très courant que vous souhaitiez répondre aux requêtes du formulaire:

Calculez pour un sous-ensemble de . $\prod_{i \in I} P(A_i)$ $I$ $\{1, \ldots n\}$

Dans ce cas, vous pouvez prétraiter vos données pour calculer tous les une seule fois et répondre à chaque requête en faisantajouts. $\log P(A_i)$ $|I|$

Enfin, la justification selon laquelle "les ordinateurs effectuent l'addition plus rapidement que la multiplication" est assez vague. Est-ce spécifique au jeu d'instructions x86, ou s'agit-il d'un trait plus fondamental des architectures de processeur?

C'est une question plus large. En général, il est (probablement?) Plus difficile de calculer la multiplication que l'addition. Le calcul de est linéaire dans la taille de et (en utilisant l'algorithme trivial), alors que nous ne savons pas actuellement comment calculer avec la même complexité temporelle (vérifiez les meilleurs algorithmes ici ). $a+b$ $a$ $b$ $a\times b$

Bien sûr, il n'y a pas de réponse définitive: par exemple, si vous ne traitez qu'avec des entiers et que vous multipliez par des puissances de , vous devriez plutôt comparer shift avec add operations. $2$

Néanmoins, c'est une déclaration raisonnable sur toutes les architectures informatiques courantes: la multiplication sur des nombres à virgule flottante sera plus lente que l'addition.

md5
la source

N'avez-vous pas également besoin de prendre en compte la complexité temporelle nécessaire pour calculer les logarithmes de toutes les probabilités

P (A_{i})

$P(A_i)$

David C

Qu'en est-il de la dernière exp ()? N'est-ce pas lent?

Mehrdad

@DavidC: Je n'ai pas essayé de calculer la complexité globale du temps. Je viens de répondre à la question "la multiplication est-elle plus rapide que l'addition". Mais en général, le logarithme informatique des nombres à virgule flottante sur une échelle logicielle peut prendre

où

est la complexité d'un algorithme de multiplication. Cela donnerait donc une complexité

(où

Θ (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$ est l'ensemble des requêtes).

md5

@Mehrdad: C'est aussi difficile que de calculer un logarithme. Cependant, je ne suis pas sûr que vous ayez besoin de le faire. Par exemple, si vous comparez uniquement les probabilités, vous préférez ne pas calculer l'

. Finale . La multiplication de

nombres dans

peut rapidement devenir très petite, donc pour la même raison que nous essayons d'éviter le sous-dépassement en utilisant les probabilités logarithmiques, nous devons rester sous la forme logarithmique à la fin (par exemple en calculant le

en base

, afin qu'il soit encore plus "lisible par l'homme").

\exp

$\exp$

n

$n$

(0, 1)

$(0,1)$

\log

$\log$

10

$10$

md5

L'addition est-elle toujours plus rapide que la multiplication si vous utilisez des flotteurs IEEE - ce que vous ferez certainement dans ce cas? Les processeurs modernes sont assez bons pour multiplier les nombres tandis que l'addition de flotteurs a quelques étapes qui ne peuvent pas être exécutées simultanément - aligner les mantisses (décaler vers la gauche en fonction du résultat de la soustraction), puis les ajouter, puis normaliser (ce qui peut déclencher à la fois un sous-dépassement et débordement, yay). En circuit, c'est beaucoup de matrices, en microcode, chaque étape coûte un cycle ou peu.

John Dvorak

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

$N$

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

Soit dit en passant, cette idée est similaire à la multiplication modulaire de Montgomery, où les multiplications sont effectuées sous la forme de Montgomery qui est assez rapide que la multiplication et la réduction habituelles.

fade2black
la source

-1 La multiplication ne prend pas de temps quadratique ...

Mehrdad

@Mehrdad, j'espère que vous avez appris la multiplication scolaire de deux nombres. Cet algorithme est encore largement utilisé sur les puces informatiques, veuillez regarder ici. Ce que vous voulez dire, ce sont des algorithmes de niveau logiciel qui sont encore pires que le temps linéaire. Ces algorithmes de multiplication sont-ils largement utilisés comme sur les circuits de multiplication?

fade2black

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

Mehrdad

L'esprit de la réponse est toujours correct, non? Si aucun des algorithmes de multiplication ne correspond au temps linéaire d'addition?

Stephen

@Stephen, en fait, la question n'était pas de savoir quelle était la meilleure complexité exacte de l'algorithme de multiplication. Je pourrais fournir des informations supplémentaires à ce sujet si des commentaires étaient nécessaires. Je pense qu'une longue discussion à ce sujet serait hors sujet ici. )))

fade2black