Jaka jest rola logarytmu w entropii Shannona?

72

Entropia Shannona jest ujemną z sumy prawdopodobieństw każdego wyniku pomnożonej przez logarytm prawdopodobieństwa każdego wyniku. Jaki cel służy logarytmowi w tym równaniu?

Intuicyjna lub wizualna odpowiedź (w przeciwieństwie do głęboko matematycznej odpowiedzi) otrzyma dodatkowe punkty!

histelheim
źródło
11
Ty (lub inni czytelnicy) mogą cieszyć się: A. Renyi (1961), On Measures of Entropy and Information , Proc. czwartego sympozjum Berkeleya na temat statystyki matematycznej i prawdopodobieństwa , vol. 1, 547–561.
kardynał
W oparciu o twoją reakcję , myślę, że masz na myśli to, dlaczego Shannon użył logarytmu w swojej formule, prawda?
Ooker
@Ooker: To jeden ze sposobów na sformułowanie tego. „Dlaczego” to umieścił? „Czym” jest jego funkcja lub rola?? „Co” osiąga? „Jak” jest pomocna? Dla mnie wszystkie znajdują się w tej samej okolicy ...
histelheim
Spójrz na moją odpowiedź tutaj: stats.stackexchange.com/questions/66186/…
kjetil b halvorsen
Zobacz moją odpowiedź, myślę, że znaczenie logu można naprawdę zrozumieć tylko poprzez zbadanie korzeni entropii Shannona w mechanice statystycznej
Aksakal

Odpowiedzi:

51

Entropia Shannona to ilość spełniająca zbiór relacji.

Krótko mówiąc, logarytm ma sprawić, że będzie rosnąć liniowo wraz z rozmiarem systemu i „zachowywać się jak informacja”.

Pierwszy oznacza, że ​​entropia rzutu monetą razy to razy entropia rzutu monetą:nn

i=12n12nlog(12n)=i=12n12nnlog(12)=n(i=1212log(12))=n.

Lub po prostu zobacz, jak to działa, gdy rzucasz dwiema różnymi monetami (być może niesprawiedliwe - z główkami z prawdopodobieństwem i ogonami dla pierwszej monety, a i dla drugiej) więc właściwości logarytmu (logarytm produktu jest sumą logarytmów) są kluczowe.p1p2q1q2

i=12j=12piqjlog(piqj)=i=12j=12piqj(log(pi)+log(qj))
=i=12j=12piqjlog(pi)i=12j=12piqjlog(qj)=i=12pilog(pi)j=12qjlog(qj)

Ale również entropia Rényi ma tę właściwość (jest to entropia parametryzowana przez liczbę rzeczywistą , która staje się entropią Shannona dla ).αα1

Nadchodzi jednak druga właściwość - entropia Shannona jest wyjątkowa, ponieważ dotyczy informacji. Aby uzyskać intuicyjne odczucie, możesz spojrzeć na jako średnią z .

H=ipilog(1pi)
log(1/p)

Możemy wywołać informacje. Dlaczego? Ponieważ jeśli wszystkie zdarzenia wystąpią z prawdopodobieństwem , oznacza to, że istnieją zdarzenia . Aby stwierdzić, które zdarzenie się wydarzyło, musimy użyć bitów (każdy bit podwaja liczbę zdarzeń, które możemy odróżnić).log(1/p)p1/plog(1/p)

Możesz odczuwać zaniepokojenie „OK, jeśli wszystkie zdarzenia mają takie samo prawdopodobieństwo, sensowne jest użycie jako miary informacji. Ale jeśli nie, to dlaczego uśrednianie informacji ma jakiś sens?” - i jest to naturalny problem.log(1/p)

Okazuje się jednak, że ma to sens - twierdzenie Shannona o kodzie źródłowym mówi, że ciąg z nieskorelowanymi literami z prawdopodobieństwami o długości nie może być skompresowany (średnio) do ciągu binarnego krótszego niż . I faktycznie, możemy użyć kodowania Huffmana do skompresowania łańcucha i zbliżenia się do .{pi}innHn HnH

Zobacz też:

Piotr Migdal
źródło
11
Ta odpowiedź ma wiele fajnych szczegółów - ale z punktu widzenia laika nadal omija problem - jaka jest rola logarytmu? Dlaczego nie możemy obliczyć entropii bez logarytmu?
histelheim
6
@histelheim Co rozumiesz przez „bez logarytmu”? jest tylko jeden. Jeśli chcesz innej miary różnorodności bez , spójrz na wskaźniki różnorodności - np. Tak zwany indeks odwrotności Simpsona który mówi efektywną liczbę wyborów (jedno ponad średnie prawdopodobieństwo), istnieje indeks Gini – Simpsona które zawsze ma wartość od 0 do jeden. A jeśli nie zależy ci na subtelnych, związanych z informacjami właściwościach entropii Shannona, możesz użyć dowolnej z nich (choć inaczej ważą niskie i wysokie prawdopodobieństwo). log 1 / i p 2 i 1 - i p 2 iipilog 1/ipi2 1ipi2
Piotr Migdal
10
Zaskakuje mnie twój ostatni komentarz, Histelheim: do czego może odnosić się „entropia bez logarytmu”? To sugeruje, że nie sformułowałeś jeszcze jasno swojego pytania, ponieważ brzmi to tak, jakbyś miał na myśli jakieś nieokreślone pojęcie „entropii”. Nie pozwól nam zgadywać - edytuj swoje pytanie, aby czytelnicy mogli udzielić odpowiedzi, których szukasz.
whuber
1
@ Piotr Migdal - piszesz „logarytm ma na celu zwiększenie jego liniowości wraz z rozmiarem systemu i„ zachowaniem się jak informacja ”. - wydaje mi się to kluczowe dla zrozumienia roli logarytmu, jednak nie jestem całkiem pewien, co to znaczy.
histelheim
1
@ Piotr Migdal - ponadto wyjaśnienie po „Możemy wywołać informacje z dziennika (1 / p). Dlaczego?” wydaje mi się mieć sens. Czy to dlatego, że logarytm zasadniczo przenosi nas z indeksu różnorodności do indeksu informacji - mierząc liczbę bitów potrzebną do rozróżnienia zdarzeń.
histelheim
25

Jest to to samo co inne odpowiedzi, ale myślę, że najlepszym sposobem na wyjaśnienie tego jest sprawdzenie, co mówi Shannon w swoim oryginalnym artykule.

Miara logarytmiczna jest wygodniejsza z różnych powodów:

  1. Jest to praktycznie bardziej przydatne. Parametry o znaczeniu inżynieryjnym, takie jak czas, szerokość pasma, liczba przekaźników itp., Zwykle zmieniają się liniowo wraz z logarytmem liczby możliwości. Na przykład dodanie jednego przekaźnika do grupy podwaja liczbę możliwych stanów przekaźników. Dodaje 1 do logarytmu podstawowego 2 tej liczby. Podwojenie czasu z grubsza kwadruje liczbę możliwych wiadomości lub podwaja logarytm itp.
  2. Jest bliżej naszego intuicyjnego odczucia co do właściwej miary. Jest to ściśle związane z (1), ponieważ intuicyjnie mierzymy jednostki poprzez liniowe porównanie ze wspólnymi standardami. Uważa się na przykład, że dwie dziurkowane karty powinny mieć dwukrotnie większą pojemność niż jedna do przechowywania informacji, a dwa identyczne kanały dwukrotnie większą niż jedna do przesyłania informacji.
  3. Jest matematycznie bardziej odpowiedni. Wiele operacji ograniczających jest prostych pod względem logarytmu, ale wymagałoby niezgrabnego przekształcenia pod względem liczby możliwości

Źródło: Shannon, A Mathematical Theory of Communication (1948) [ pdf ].


Zauważ, że entropia Shannona pokrywa się z entropią mechaniki statystycznej Gibbsa, a także wyjaśnienie, dlaczego log występuje w entropii Gibbsa. W mechanice statystycznej entropia ma być miarą liczby możliwych stanów w których można znaleźć układ. Powodem, dla którego jest lepszy niż jest to, że jest zwykle bardzo szybko rosnącą funkcją swoich argumentów, a więc nie może być użytecznie przybliżona przez rozwinięcie Taylora, podczas gdy może być. (Nie wiem, czy to była pierwotna motywacja do podjęcia dziennika, ale wyjaśniono to w wielu wstępnych książkach z fizyki).log Ω Ω Ω log ΩΩlogΩΩΩlogΩ

Flądrarz
źródło
Ta odpowiedź wydaje się być jak najbardziej skoncentrowana, ale zawiera wiele informacji.
jasna gwiazda
1
Nie dlatego dziennik pojawia się w obliczeniach entropii. Dlatego zgłoszone informacje są zgłaszane jako takie. Istnieje alternatywna ilość: „zakłopotanie”, które zgłasza informacje bez dziennika. W tej części swojego artykułu Shannon opowiada się za bitami / kotami / hartleyami i przeciw zakłopotaniu.
Neil G,
15

inny sposób patrzenia na to jest z algorytmicznego punktu widzenia. Wyobraź sobie, że idziesz do odgadnięcia numer , że jedyną informacją jest to, że masz ten numer jest w przedziale . W tej sytuacji optymalnym algorytmem do zgadywania liczby jest prosty algorytm wyszukiwania binarnego , który znajduje w kolejności . Ta formuła intuicyjnie określa, ile pytań musisz zadać, aby dowiedzieć się, co to jest . Na przykład, jeśli , musisz zadać maksymalnie 3 pytania, aby znaleźć nieznane .1 x N x O ( log 2 N ) x N = 8 xx1xNxO(log2N)xN=8x

Z punktu widzenia prawdopodobieństwa, kiedy deklarowania jako równie mogą być dowolne wartości w zakresie , to znaczy o . Claude Shannon ładnie pokazał, że zawartość informacyjna wyniku jest zdefiniowana jako:1 x N p ( x ) = 1 / N 1 x N xx1xNp(x)=1/N1xNx

h(x)=log21p(x)

Powodem dla podstawy 2 w logarytmie jest to, że tutaj mierzymy informacje w bitach . Możesz także założyć logarytm naturalny, który sprawia, że ​​informacje są mierzone w nats . Na przykład zawartość informacyjna outcom wynosi . Ta wartość jest dokładnie równa liczbie kroków w algorytmie wyszukiwania binarnego (lub liczbie instrukcji IF w algorytmie). Dlatego liczba pytań, które musisz znaleźć jest równa , jest dokładnie informacyjną zawartością wyniku .x=4h(4)=3x4x=4

Możemy również przeanalizować wydajność algorytmu wyszukiwania binarnego dla każdego możliwego wyniku. Jednym ze sposobów jest sprawdzenie, jaka jest oczekiwana liczba pytań, które należy zadać dla dowolnej wartości . Zauważ, że liczba wymaganych pytań do odgadnięcia wartości , jak omówiłem powyżej, to . Dlatego oczekiwana liczba pytań dla dowolnego jest z definicji równa:xxh(x)x

h(x)=1xNp(x)h(x)

Oczekiwana liczba pytań jest dokładnie taka sama jak entropia zbioru , lub w skrócie entropia. Dlatego można stwierdzić, że entropii ilościowo oczekiwano (lub średnia) liczbę pytań jedno trzeba prosić, aby odgadnąć wynik, który jest złożoność obliczeniowa wyszukiwanie binarne.h(x)H(X)H(X)

omidi
źródło
1
+ To jedno z moich ulubionych zastosowań teorii informacji - analiza algorytmów. Jeśli masz punkty decyzyjne z> 2 wynikami, na przykład podczas indeksowania tablicy, jest to zasada kodowania mieszającego i sortowania O (n).
Mike Dunlavey
Ten argument jest odpowiedni dla dyskretnej entropii, ale nie łatwo uogólnić na ciągłą entropię.
Neil G,
12

Oto proste wyjaśnienie. Można powiedzieć, że 2 książki tego samego rozmiaru zawierają dwa razy więcej informacji niż 1 książka, prawda? (Uważając książkę za ciąg bitów.) Cóż, jeśli pewien wynik ma prawdopodobieństwo P, to można powiedzieć, że jego zawartość informacyjna dotyczy liczby bitów, które należy zapisać 1 / P. (np. jeśli P = 1/256, to 8 bitów.) Entropia jest tylko średnią długości tej bitu informacji, dla wszystkich wyników.

Mike Dunlavey
źródło
5

Celem pojawiającego się w Entropii Shannona jest to, że jest jedyną funkcją spełniającą podstawowy zestaw właściwości, które jest w stanie ująć funkcja entropii, .log ( p i ) H ( p 1 , , p N )log(pi)log(pi)H(p1,,pN)

Shannon przedstawił matematyczny dowód tego wyniku, który został gruntownie wybrany i powszechnie przyjęty. Cel i znaczenie logarytmu w równaniu entropijnym jest zatem samowystarczalne w ramach założeń i dowodu.

Nie ułatwia to zrozumienia, ale ostatecznie jest powodem, dla którego pojawia się logarytm.

Znalazłem następujące odniesienia przydatne oprócz tych wymienionych gdzie indziej:

  1. Teoria prawdopodobieństwa: logika nauki autorstwa ET Jaynesa . Jaynes jest jednym z niewielu autorów, który czerpie wiele wyników od zera; patrz rozdział 11.
  2. Teoria informacji, wnioskowanie i algorytmy uczenia się David MacKay. Zawiera dogłębną analizę twierdzenia Shannona o kodowaniu źródłowym; patrz rozdział 4.
użytkownik119961
źródło
4

Podsumowanie:

nn

Przykład:

661n=21

3.56/2=3

1

Zróbmy to:

  • 6>3.5
  • 6/2=35
  • 6/2/2=1.5=6

63ceil(log2(6))=ceil(2.58)=3

ceil

2.58

log2(...)n2 log n ( . . . )n2logn(...)

Symulacja:

import random

total_questions = 0
TOTAL_ROUNDS = 10000

for i in range(0,TOTAL_ROUNDS):
    outcome = random.randrange(1,7)
    total_questions += 1
    if outcome > 3.5:
        total_questions += 1
        if outcome >= 5:
            total_questions += 1
            if outcome == 5:
                pass
            else:
                # must be 6! no need to ask
                pass
        else:
            # must be 4! no need to ask
            pass
    else:
        total_questions += 1
        if outcome >= 2:
            total_questions += 1
            if outcome == 2:
                pass
            else:
                # must be 3! no need to ask
                pass
        else:
            # must be 1! no need to ask
            pass


print 'total questions: ' + str(total_questions)
print 'average questions per outcome: ' + str(total_questions/float(TOTAL_ROUNDS))

Wyniki:

total questions: 26634
average questions per outcome: 2.6634

2.6634log2(6)2.58

Co jest nie tak? Jest prawie blisko, ale nie bardzo blisko, jak się spodziewałem. Czy to PRNG Pythona próbuje powiedzieć wolny żart? A może Shannon się myli? A może to - Boże, zabrania - moje rozumienie jest błędne? Tak czy inaczej POMOC. SOS już stary.

jaskiniowiec
źródło
2
65=7776log2(65)=1313/5=2.6190537492531492531/1905372.584962500722
@ whuber czy nie to robię w kodzie? Rzucam 10000 kostkami i sumuję całkowitą liczbę pytań, które zadaję dla wszystkich kostek. Następnie sumę / 10000 otrzymuję 2,66.
jaskiniowiec
1
Nie, wcale tego nie robisz w swoim kodzie! Musisz zadać zestaw pytań zaprojektowanych tak, aby jednocześnie uzyskać stan wszystkich kości jednocześnie. To nie to samo, co średnia liczba pytań potrzebnych do znalezienia stanu jednej śmierci na raz.
whuber
3

Ω={ω1,,ωn}p1,,pnH(p1,,pn)

  • H
  • Hnp1==pn=1n
  • H
    H(12,16,13)=H(12,12)+12H(13,23).

H

H(p1,,pn)=i=1npilogkpi
k>1k=2
Neil G.
źródło
3

To pytanie powstało dwa lata temu i było już wiele niesamowitych odpowiedzi, ale chciałbym dodać moje, które bardzo mi pomogło.

Pytanie brzmi

Jaki cel służy logarytmowi w tym równaniu?

Logarytm (zwykle oparty na 2) wynika z nierówności Krafta .

i=1m2li<=1

liLxP(x)

P(x)=2L(x)

L(x)=logP(x)P(x)L(x)

L(x)P(x)P(x)logP(x)

Intuicyjny ilustracji i wizualny odpowiedź (jak jest to wymagane, ale specjalnie dla Krafta nierówności) jest wyrażona w tym artykule kod drzewa i Nierówność Krafta .

Lerner Zhang
źródło
1

W oparciu o twoją nieakceptację jakichkolwiek odpowiedzi, myślę, że to, czego szukasz, jest powodem, dla którego Shannon w pierwszej kolejności zastosował logarytm w swojej formule. Innymi słowy, jego filozofia.

Oświadczenie : Jestem na tym polu tylko przez tydzień, przychodzę tutaj z powodu pytania takiego jak ty . Jeśli masz więcej wiedzy na ten temat, daj mi znać.

Mam to pytanie po przeczytaniu jednego z najważniejszych artykułów Ulanowicza, Rosnąca Entropia: śmierć z powodu upałów czy wieczne harmonie? . W tym akapicie wyjaśniono, dlaczego formuła ma -log (p) zamiast (1-p):

Przed dalszym rozpakowaniem formalnej definicji entropii należałoby zapytać, dlaczego nie wybrać po prostu (1 - p) zamiast [–log (p)] jako najbardziej odpowiedniej miary nieistnienia? Odpowiedź jest następująca: wynikowy iloczyn p (czyli [p – p ^ 2]) jest idealnie symetryczny wokół wartości p = 0,5. Obliczenia według takiej symetrycznej kombinacji byłyby w stanie opisać tylko odwracalny wszechświat. Boltzmann i Gibbs starali się jednak określić ilościowo nieodwracalny wszechświat. Wybierając jednoczynnikową wypukłą funkcję logarytmiczną, Boltzmann nadał w ten sposób uprzedzenie niebycie nad bytem. Zauważono na przykład, że max [–xlog {x}] = {1 / e} ≈ 0,37, tak że miara nieokreśloności jest wypaczana w kierunku niższych wartości pi.

Wygląda na to, że Shannon wybrał logarytm bez powodu. Po prostu „pachniał”, że powinien używać logarytmu. Dlaczego Newton wybrał operację zwielokrotnienia w swojej formule F = m * a?

Zauważ, że w tym czasie nie miał pojęcia o entropii :

Moją największą troską było to, jak to nazwać. Myślałem o nazwaniu go „informacją”, ale słowo to było zbyt często używane, dlatego postanowiłem nazwać je „niepewnością”. Kiedy rozmawiałem o tym z Johnem von Neumannem, miał lepszy pomysł. Von Neumann powiedział mi: „Powinieneś nazwać to entropią z dwóch powodów. Po pierwsze, twoja funkcja niepewności została użyta w mechanice statystycznej pod tą nazwą, więc ma już nazwę. Po drugie i, co ważniejsze, nikt nie wie, czym tak naprawdę jest entropia, więc w debacie zawsze będziesz miał przewagę.

Moja odpowiedź brzmi: nie ma tego powodu. Wybrał to, ponieważ po prostu magicznie działało.

Ooker
źródło
0

Entropia jest zdefiniowana jako logarytm średniej geometrycznej współczynnika wielomianowego, który wyraża liczbę stanów, w których może znajdować się system:

log(Nn1,,nk)N

Logarytmy pojawiają się we wzorze po zastosowaniu aproksymacji silniowej Stirlinga (patrz to objaśnienie )

Atamiri
źródło
3
Wierzę, że PO wie, że logarytm jest częścią definicji. Pytają, dlaczego tam jest?
whuber
0

Dziennik pochodzi z wyprowadzenia funkcji H spełniającej określone wymagania naturalne. Patrz str. 3 sek. 2 tego źródła:

http://www.lptl.jussieu.fr/user/lesne/MSCS-entropy.pdf

Biorąc pod uwagę aksjomaty, jeśli przeprowadzisz optymalizację, otrzymasz unikalną (upto stałą) funkcję z logiem.

Wszystkie powyższe odpowiedzi są poprawne, z wyjątkiem tego, że interpretują dziennik, ale nie wyjaśniają jego źródła.

Swapnil Bhatia
źródło
0

Wydaje mi się, że twoje pytanie dotyczy bardziej „znaczenia” tego logarytmu i dlaczego każdy element przyczynia się do ogólnego znaczenia formuły, a nie zwykłego formalizmu pokazującego spójność definicji z pewnymi wymaganiami.

p(x)log(p(x))

  • p(x)
  • log(p(x))

p(x)log(p(x))


Odtąd będę omawiać, w jaki sposób OGÓLNOŚĆ wpływa na ostateczną formułę entropii.

log2(x)=number_of_bits_to_encode_the_messages

Teraz usiądź, zrelaksuj się i popatrz, jak pięknie Entropy Shannona robi tę sztuczkę: opiera się na (rozsądnym) założeniu, że wiadomości, które są bardziej OGÓLNE, są w związku z tym częstsze.

Na przykład powiem, że pada deszcz, jeśli jest to średni, obfity lub bardzo ciężki deszcz. Dlatego zaproponował zakodowanie OGÓLNEJ wiadomości w oparciu o ich CZĘSTOTLIWOŚĆ ... i proszę bardzo:

log2N=log21/N=log2P

Nx

Równanie można interpretować jako: rzadkie wiadomości będą miały dłuższe kodowanie, ponieważ są mniej ogólne, więc potrzebują więcej bitów do zakodowania i są mniej pouczające. Dlatego posiadanie bardziej szczegółowych i rzadkich wiadomości przyczyni się bardziej do entropii niż posiadanie wielu wiadomości ogólnych i częstych.


p(x)log(p(x))

Najwyższą entropią jest sytuacja, gdy mamy system z wieloma rzadkimi i specyficznymi komunikatami. Najniższa entropia z częstymi i ogólnymi komunikatami. W międzyczasie mamy spektrum systemów równoważnych entropii, które mogą mieć zarówno rzadkie, jak i ogólne komunikaty lub częste, ale konkretne komunikaty.

Gabrer
źródło
0

Nie sądzę, że można udzielić uniwersalnej „intuicyjnej” odpowiedzi. Dam ci odpowiedź intuicyjną dla niektórych osób, takich jak fizycy. Logarytm ma na celu uzyskanie średniej energii systemu. Oto szczegóły.

Shannon użył słowa „ entropia ”, ponieważ zaadaptował to pojęcie z mechaniki statystycznej . W mechanice statystycznej występuje przełomowy rozkład nazwany na cześć Boltzmanna. Co ciekawe, jest to obecnie ważna dystrybucja w uczeniu maszynowym!

P=eaEb
a,bEdVVdV=dpdxx,pa,bVPdV=1b odpowiada temperaturze systemu.

lnPE

SVPlnPdV=<E>

η=iPilnPi
ePi

Czy to jest dla Ciebie wystarczająco intuicyjne? To dla mnie, ale byłem fizykiem teoretycznym w poprzednim życiu. Możesz także przejść do głębszego poziomu intuicji, łącząc się z jeszcze starszymi koncepcjami termodynamicznymi, takimi jak temperatura i twórczość Boltzmanna i Clausiusa.

Aksakal
źródło