Dlaczego dodawanie prawdopodobieństw dziennika jest szybsze niż pomnożenie prawdopodobieństw?

Aby sformułować pytanie, w informatyce często chcemy obliczyć iloczyn kilku prawdopodobieństw:

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

Najprostszym podejściem jest po prostu pomnożenie tych liczb i właśnie to zamierzałem zrobić. Jednak mój szef powiedział, że lepiej jest dodać dziennik prawdopodobieństwa:

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

Daje to prawdopodobieństwo dziennika, ale w razie potrzeby możemy je później uzyskać:

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

Dodawanie dziennika jest uważane za lepsze z dwóch powodów:

Zapobiega „niedomiarowi”, przez co iloczyn prawdopodobieństwa jest tak mały, że zostaje zaokrąglony do zera. Może to często stanowić ryzyko, ponieważ prawdopodobieństwo jest często bardzo małe.
Jest to szybsze, ponieważ wiele architektur komputerowych może wykonywać dodawanie szybciej niż mnożenie.

Moje pytanie dotyczy drugiej kwestii. Tak to widziałem, ale nie bierze ono pod uwagę dodatkowych kosztów uzyskania dziennika! Powinniśmy porównać „koszt dziennika + koszt dodania” do „kosztu pomnożenia”. Czy po uwzględnieniu tego jest jeszcze mniejszy?

Strona Wikipedii ( prawdopodobieństwo dziennika ) jest pod tym względem myląca, mówiąc: „Konwersja do postaci dziennika jest kosztowna, ale następuje tylko raz”. Nie rozumiem tego, ponieważ myślę, że musisz dodać dziennik każdego terminu niezależnie przed dodaniem. czego mi brakuje?

Wreszcie uzasadnienie, że „komputery wykonują dodawanie szybciej niż mnożenie” jest niejasne. Czy jest to specyficzne dla zestawu instrukcji x86, czy może jest to bardziej fundamentalna cecha architektury procesorów?

algorithm-analysis probability-theory Stephen
źródło

Pierwsza korzyść (unikanie niedomiaru) jest często o wiele ważniejsza niż wzrost wydajności, więc nawet jeśli nie byłoby to szybsze, nadal używalibyśmy prawdopodobieństw dziennika.

Aby rozwinąć to, co powiedział @DW, istnieje podobna „sztuczka log-sum-exp” używana specjalnie w celu rozwiązania problemu niedomiaru, bez względu na wydajność. W rzeczywistości po raz pierwszy widziałem, że ktoś uważa logarytmy za technikę poprawy wydajności!

Mehrdad

Odpowiedzi:

Również strona Wikipedii ( https://en.wikipedia.org/wiki/Log_probability ) jest myląca pod tym względem, stwierdzając: „Konwersja do postaci dziennika jest kosztowna, ale następuje tylko raz”. Nie rozumiem tego, ponieważ myślę, że musisz dodać dziennik każdego terminu niezależnie przed dodaniem. czego mi brakuje?

Jeśli chcesz tylko raz obliczyć , masz rację. Będziesz musiał obliczyć logarytmów i dodatków, podczas gdy naiwna metoda wymaga multiplikacji. $P(A_1)\ldots P(A_n)$ $n$ $n-1$ $n-1$

Jednak często zdarza się, że chcesz odpowiadać na zapytania formularza:

Oblicz dla niektórych podzbiorów z . $\prod_{i \in I} P(A_i)$ $I$ $\{1, \ldots n\}$

W takim przypadku możesz wstępnie przetworzyć swoje dane, aby obliczyć wszystkie tylko raz i odpowiedzieć na każde zapytanie, wykonując wzbogacenie. $\log P(A_i)$ $|I|$

Wreszcie uzasadnienie, że „komputery wykonują dodawanie szybciej niż mnożenie” jest niejasne. Czy jest to specyficzne dla zestawu instrukcji x86, czy może jest to bardziej fundamentalna cecha architektury procesorów?

To jest szersze pytanie. Zasadniczo (prawdopodobnie?) Trudniej jest obliczyć mnożenie niż dodawanie. Obliczanie jest liniowa w rozmiarze i (przy użyciu algorytmu trywialne), natomiast obecnie nie wiem jak obliczyć o tej samej złożoności czasowej (Sprawdź najlepsze algorytmy tutaj ). $a+b$ $a$ $b$ $a\times b$

Oczywiście nie ma ostatecznej odpowiedzi: na przykład, jeśli masz do czynienia tylko z liczbami całkowitymi i mnożymy przez potęgi , powinieneś raczej porównać shift z operacjami dodawania. $2$

Niemniej jednak jest to rozsądne stwierdzenie na wszystkich popularnych architekturach komputerowych: mnożenie liczb zmiennoprzecinkowych będzie wolniejsze niż dodawanie.

md5
źródło

P (A_{i})

$P(A_i)$

Co z końcowym exp ()? Czy to nie jest wolne?

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$ to zestaw zapytań).

md5

\exp

$\exp$

n

$n$

(0, 1)

$(0,1)$

\log

$\log$

10

$10$

Czy dodawanie jest jeszcze szybsze niż mnożenie, jeśli używasz pływaków IEEE - co z pewnością zrobisz w tym przypadku? Nowoczesne cpus są całkiem dobre w pomnażaniu liczb, podczas gdy dodawanie zmiennoprzecinkowe ma kilka kroków, których nie można wykonać jednocześnie - wyrównaj mantysy (przesuń w lewo na podstawie wyniku odejmowania), a następnie dodaj je, a następnie normalizuj (co może powodować zarówno niedopełnienie, jak i przepełnienie, tak). W obwodzie jest dość dużo matrycy, w mikrokodzie każdy krok kosztuje cykl lub kilka.

John Dvorak

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

$N$

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

Nawiasem mówiąc, ten pomysł jest podobny do modularnego mnożenia Montgomery, w którym mnożenia są wykonywane w postaci Montgomery, która jest znacznie szybsza niż zwykłe mnożenie, a następnie redukcja.

fade2black
źródło

-1 Mnożenie nie zajmuje czasu kwadratowego ...

Mehrdad

@ Mehrdad, mam nadzieję, że nauczyłeś się szkolnego mnożenia dwóch liczb. Że algorytm jest nadal szeroko stosowany w układach komputerowych, spójrz tutaj. Masz na myśli algorytmy na poziomie oprogramowania, które są gorsze niż czas liniowy. Czy te algorytmy mnożenia są powszechnie stosowane jak w obwodzie mnożenia?

fade2black

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

Mehrdad

Duch odpowiedzi jest jednak nadal poprawny, prawda? Jeśli żaden z algorytmów mnożenia nie będzie pasował do liniowego czasu dodawania?

Stephen

@ Stephen, w rzeczywistości pytanie nie dotyczyło dokładnej najlepszej złożoności algorytmu mnożenia. Mógłbym udzielić dodatkowych informacji na ten temat, jeśli komentatorzy tego wymagają. Myślę, że długa dyskusja na ten temat byłaby tutaj nie na temat. )))

fade2black