Warum ist das Hinzufügen von Protokollwahrscheinlichkeiten schneller als das Multiplizieren von Wahrscheinlichkeiten?

Um die Frage zu formulieren, wollen wir in der Informatik häufig das Produkt mehrerer Wahrscheinlichkeiten berechnen:

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

Am einfachsten ist es, diese Zahlen einfach zu multiplizieren, und genau das wollte ich tun. Mein Chef sagte jedoch, es sei besser, das Protokoll der Wahrscheinlichkeiten hinzuzufügen:

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

Dies gibt die Log-Wahrscheinlichkeit an, aber wir können die Wahrscheinlichkeit bei Bedarf nachträglich ermitteln:

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

Das Hinzufügen von Protokollen wird aus zwei Gründen als besser angesehen:

Es verhindert "Unterlauf", wobei das Produkt der Wahrscheinlichkeiten so klein ist, dass es auf Null gerundet wird. Dies kann häufig ein Risiko darstellen, da die Wahrscheinlichkeiten häufig sehr gering sind.
Es ist schneller, da viele Computerarchitekturen die Addition schneller ausführen können als die Multiplikation.

Meine Frage betrifft den zweiten Punkt. So habe ich es beschrieben gesehen, aber es berücksichtigt nicht die zusätzlichen Kosten für das Abrufen des Protokolls! Wir sollten "Kosten für Log + Kosten für Addition" mit "Kosten für Multiplikation" vergleichen. Ist es noch kleiner, wenn man das berücksichtigt?

Auch die Wikipedia-Seite ( Log-Wahrscheinlichkeit ) ist in dieser Hinsicht verwirrend und besagt: "Die Konvertierung in die Log-Form ist teuer, fällt aber nur einmal an." Ich verstehe das nicht, weil ich denke, dass Sie vor dem Hinzufügen das Protokoll jedes Begriffs unabhängig erstellen müssten. Was vermisse ich?

Schließlich ist die Rechtfertigung, dass "Computer Additionen schneller ausführen als Multiplikationen", etwas vage. Ist das spezifisch für den x86-Befehlssatz oder ist es eine grundlegendere Eigenschaft von Prozessorarchitekturen?

algorithm-analysis probability-theory Stephen
quelle

Der erste Vorteil (Vermeidung von Unterlauf) ist oft viel wichtiger als der Leistungszuwachs. Selbst wenn er nicht schneller wäre, würden wir trotzdem Log-Wahrscheinlichkeiten verwenden.

Um das, was @DW gesagt hat, zu erweitern, gibt es einen ähnlichen "Log-Sum-Exp-Trick", der speziell zur Behebung von Unterläufen verwendet wird, ohne Rücksicht auf die Leistung. Tatsächlich war es das erste Mal, dass jemand Logarithmen als eine Technik zur Leistungsverbesserung ansah!

Mehrdad

Antworten:

Auch die Wikipedia-Seite ( https://en.wikipedia.org/wiki/Log_probability ) ist in dieser Hinsicht verwirrend und besagt: "Die Konvertierung in ein Protokollformular ist teuer, fällt jedoch nur einmal an." Ich verstehe das nicht, weil ich denke, dass Sie vor dem Hinzufügen das Protokoll jedes Begriffs unabhängig erstellen müssten. Was vermisse ich?

Wenn Sie nur einmal berechnen möchten , dann haben Sie Recht. Sie müssen Logarithmen und Additionen berechnen , während die naive Methode Multiplikationen erfordert . $P(A_1)\ldots P(A_n)$ $n$ $n-1$ $n-1$

Es ist jedoch sehr häufig, dass Sie Fragen des Formulars beantworten möchten:

Berechnen Sie für eine Teilmenge von . $\prod_{i \in I} P(A_i)$ $I$ $\{1, \ldots n\}$

In diesem Fall können Sie Ihre Daten vorverarbeiten, um das gesamte nur einmal zu berechnen , und jede Abfrage mit beantworten Ergänzungen. $\log P(A_i)$ $|I|$

Schließlich ist die Rechtfertigung, dass "Computer Additionen schneller ausführen als Multiplikationen", etwas vage. Ist das spezifisch für den x86-Befehlssatz oder ist es eine grundlegendere Eigenschaft von Prozessorarchitekturen?

Dies ist eine weiter gefasste Frage. Im Allgemeinen ist es (wahrscheinlich?) Schwieriger, die Multiplikation zu berechnen als die Addition. Die Berechnung von ist linear in der Größe von und (unter Verwendung des trivialen Algorithmus), wohingegen wir derzeit nicht wissen, wie man mit der gleichen zeitlichen Komplexität berechnet (überprüfen Sie die besten Algorithmen hier ). $a+b$ $a$ $b$ $a\times b$

Natürlich gibt es keine definitive Antwort: zum Beispiel , wenn Sie mit ganzen Zahlen beschäftigen nur und Sie vermehren sich durch Potenzen von , dann sollten Sie eher Verschiebung mit Zusatzoperationen vergleichen. $2$

Dies ist jedoch eine vernünftige Aussage für alle gängigen Computerarchitekturen: Die Multiplikation mit Gleitkommazahlen ist langsamer als die Addition.

md5
quelle

Müssen Sie nicht auch die Zeitkomplexität berücksichtigen, die erforderlich ist, um die Logarithmen für alle Wahrscheinlichkeiten

zu berechnen ?

P (A_{i})

$P(A_i)$

David C

Was ist mit der finalen exp ()? Ist das nicht langsam?

Mehrdad

@DavidC: Ich habe nicht versucht, die Gesamtzeitkomplexität zu berechnen. Ich habe gerade auf die Frage geantwortet "ist die Multiplikation schneller als die Addition". Im Allgemeinen kann der Berechnungslogarithmus von Gleitkommazahlen auf einer Softwareskala jedoch

annehmen, wobei

die Komplexität eines Multiplikationsalgorithmus ist. So ist es eine geben würde

Komplexität (wobei

Θ (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$ ist die Menge der Abfragen).

md5

@Mehrdad: Es ist so schwierig wie einen Logarithmus zu berechnen. Ich bin mir jedoch nicht sicher, ob Sie das jemals tun müssen. Wenn Sie beispielsweise nur Wahrscheinlichkeiten vergleichen, möchten Sie die endgültige

. Nicht berechnen . Die Multiplikation von

Zahlen in

\exp

$\exp$

n

$n$

kann schnell sehr klein werden. Aus dem gleichen Grund, aus dem wir versuchen, einen Unterlauf durch Verwendung von Log-Wahrscheinlichkeiten zu vermeiden, sollten wir am Ende in der logarithmischen Form bleiben (z. B. durch Berechnen des

in Basis

, damit es noch "lesbarer" ist).

(0, 1)

$(0,1)$

\log

$\log$

10

$10$

md5

Ist die Addition noch schneller als die Multiplikation, wenn Sie IEEE-Floats verwenden - was Sie in diesem Fall sicherlich tun werden? Moderne CPUs sind ziemlich gut darin, Zahlen zu multiplizieren, wohingegen die Float-Addition einige Schritte umfasst, die nicht gleichzeitig ausgeführt werden können - richten Sie Mantissen aus (Verschiebung nach links basierend auf dem Ergebnis der Subtraktion), addieren Sie sie dann tatsächlich und normalisieren Sie sie (was sowohl einen Unterlauf als auch einen Unterlauf auslösen kann) Überlauf, yay). In der Schaltung ist es ziemlich viel Würfel, im Mikrocode kostet jeder Schritt einen Zyklus oder wenige.

John Dvorak

Mit "einmal angefallen" ist wahrscheinlich gemeint, dass wenn Sie $N$ $p_1,...p_N$ $p_i$

$N$

Schließlich ist die Addition schneller als die Multiplikation, nicht wegen der Maschinenarchitektur. Die Addition ist von Natur aus schneller als die Multiplikation. In Bezug auf die Komplexität braucht es $O(n)$ $n$ $O(n^2)$

Diese Idee ähnelt im Übrigen der modularen Multiplikation nach Montgomery, bei der Multiplikationen in der Montgomery-Form durchgeführt werden, die viel schneller ist als die übliche Multiplikation und anschließende Reduktion.

fade2black
quelle

-1 Multiplikation braucht keine quadratische Zeit ...

Mehrdad

@Mehrdad, ich hoffe, Sie haben die Schulmultiplikation mit zwei Zahlen gelernt. Dass Algorithmus auf Computerchips immer noch weit verbreitet ist , sehen Sie hier. Was Sie meinen, sind Algorithmen auf Softwareebene, die immer noch schlechter als die lineare Zeit sind. Sind diese Multiplikationsalgorithmen weit verbreitet wie bei Multiplikationsschaltungen?

fade2black

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

Mehrdad

Der Geist der Antwort ist aber immer noch richtig, oder? Wenn keiner der Multiplikationsalgorithmen mit der linearen Additionszeit übereinstimmt?

Stephen

@Stephen, in der Tat ging es nicht darum, was genau die beste Komplexität des Multiplikationsalgorithmus ist. Ich könnte zusätzliche Informationen zu diesem Thema zur Verfügung stellen, wenn Kommentatoren benötigt werden. Ich denke, dass eine lange Diskussion darüber hier nicht zum Thema gehören würde. )))

fade2black