Entropie berechnen oder schätzen unterschiedliche Werte

Jay1980

Hi,

ich kann mir gerade dies nicht erklären: ich will die Entropie berechnen, das klappt wenn ich das manuell mache ganz ok, für den String YYYF bei einem Alphabet von 20 Zeichen (Alphabetumfang spielt in dem Beispiel denke ich keine Rolle) erhalte ich eine Entropie von ungefähr 0.56.

Schau ich mich aber im Internet nach Shannon-Entropie-Berechnungsimplementierungen um, dann wird da oft was von 'Schätzen' erwähnt, dazu kann man diverse Algorithmen aussuchen und jetzt kommt das, was mich beunruhigt: es kommt 1.67 raus statt meiner 0.56.

Ich habe aufgepasst, dass es nicht an der verwendeten Algorithmuskonfiguration liegt, ich verwende beide Male den natürlichen Algorithmus. Ich verstehe auch nicht, warum dort in den R-internen Funktionen von Schätzen gesprochen wird, ich habe doch alles und will gar nicht von einer Stichprobe auf die Grundgesamtheit schließen - das verbinde ich nämlich mit Schätzen. Ich will die Shannon-Entropie für einen String berechnen - fertig.

Was ist da los?

Danke vorab.

Ich rechne so:

# Entropy manuell
s <- "YYYF" # die Zeichenkette
e <- 0.0    # Startwert
s1 <- 0.75  # relativer Anteil Symbol 1 hier 75 %
ls1 <- log(s1)
p1 <- -( s1 * ls1)
e <- e + p1
s2 <- 0.25  # relativer Anteil Symbol 2 hier 25 %
ls2 <- log(s2)
p2 <- -( s2 * ls2)
e <- e + p2
print( "Ergebnis manuell:" )
print( e ) # wie erwartet 0.56

# R Funktion
t1 <- "YYYF"
yt1 <- c( 0.75, 0.25, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 )
et1 <- entropy( yt1, method="CS", unit="log")

# Ergebnisausgabe
[1] "Ergebnis manuell:"
[1] 0.5623351
[1] "Entropie:"
[1] 1.673976

Das R-Paket zur Entropie-Berechnung ist etwa hier: http://strimmerlab.org/software/entropy/

Danke vorab, falls einer für Aufklärung sorgen kann.

Ich habe mir nicht ganz genau angeschaut, was du da alles gerechnet hast.
ABer die Entropie ist doch - summe_n p_n log_2(p_n)
WObei p_n die Auftrittswahrscheinlichkeit des n-ten Zeichens ist.

Dafür muss ich dann aber Auftrittswahrscheinlichkeiten kennen.

Wenn ich mal so tue, als wären alle Zeichen gleichwahrscheinlich, ist bei dir p_n=1/20

Damit ist dann die Entopie -4*(1/20)*log_2(1/20) = 0.86....

Jay1980

Hm,

die Auftrittswahrscheinlichkeit ist aber denke ich in diesem Fall gleichbedeutend mit dem relativen Auftreten, also 0.75 für Y, da 3 aus 4 Symbolen. Das Alphabet für diesen Spaltenstring ist nämlich nur 2, das wurde mir nun klar, als ich über deine Antwort nachdachte. Es gibt zwar 20 Symbole, aber jeder String wird für sich völlig separat betrachtet, und die Chance dass sich da ein anderes Symbol einschleichen könnte ist gleich 0.

Die Basis des Logarithmus kann wohl variieren, je nachdem ob man dann den Entropie-Wert in der Einheit bit haben will, da muss man dann wohl log_2 nehmen. In meinem Fall brauche ich aber log_n laut Formel.

Jester

wieso gerade dieser schätzer? probiers mal mit entropy.empirical, das scheint eher die funktion zu sein, die du suchst.

Jay1980

Okay,

entropy.empirical liefert mir zumindest das Ergebnis, welches ich erwarte.

@Jester wie kamst du darauf, dass ich gerade diese Variante brauche?

Hier noch der Link zu dieser Variante der Doku:
http://www.oga-lab.net/RGM2/func.php?rd_id=entropy:entropy.empirical

R-Code:
library(entropy)
t1 <- "YYYF"
yt1 <- c( 0.75, 0.25 )
et1 <- entropy.empirical( yt1, unit="log")

print( "Entropie aus R-Funktion:")
print( et1 )
#t1exp <- 0.562335; // aus Java 0.5623351446188083;

Jay1980 schrieb:

Hm,

die Auftrittswahrscheinlichkeit ist aber denke ich in diesem Fall gleichbedeutend mit dem relativen Auftreten, also 0.75 für Y, da 3 aus 4 Symbolen. Das Alphabet für diesen Spaltenstring ist nämlich nur 2, das wurde mir nun klar, als ich über deine Antwort nachdachte. Es gibt zwar 20 Symbole, aber jeder String wird für sich völlig separat betrachtet, und die Chance dass sich da ein anderes Symbol einschleichen könnte ist gleich 0.

Das ist eine Frage, was du modellieren willst. Entropie ist anschaulich ein Maß für die "Überraschung" mit dem ein Symbol auftritt. Angenommen, ich lesen einen Text in deutscher Sprache. Dann bin ich über jedes "y" ziemlich überrascht. Wenn der Text aber Englisch ist, dann bin ich plötzlich viel weniger über ein "y" überrascht.

Die Frage ist hier, was für Annahmen du machst über die Wahrscheinlichkeiten deiner Symbole. Wenn die einzigen Informationen, die du hast, nur diese 4 Buchstaben sind, muss man Wahrscheinlichkeiten raten. Wenn du zb den Text komprimieren willst, ist deine Annahme super (weil du mit deinen Wahrscheinlichkeiten nie wieder auf einen anderen text anwenden wirst als deine 4 Buchstaben). Wenn du die Entropie dieser vier Buchstaben mit der Entropie von anderen Wörtern über dem gleichen Alphabet vergleichen willst, müsstest du entweder eine Statistik über alle diese Wörter machen, falls du alle diese Wörter schon von Anfang an kennst. Falls du keine anderen Wörter zu dieser Zeit kennst, wäre eine Gleichverteilung vielleicht eine anständige Annahme.

Jay1980 schrieb:

Die Basis des Logarithmus kann wohl variieren, je nachdem ob man dann den Entropie-Wert in der Einheit bit haben will, da muss man dann wohl log_2 nehmen. In meinem Fall brauche ich aber log_n laut Formel.

Die Basis ist ziemlich egal. Das macht nur einen konstanten Faktor als unterschied.

Jester

weil ich "empirical" so verstehe, dass es rein statistisch auf den Häufigkeiten im sample arbeitet, während alles andere ausgefeiltere Schätzer sind.

Jay1980

Mups schrieb:

Die Frage ist hier, was für Annahmen du machst über die Wahrscheinlichkeiten deiner Symbole. Wenn die einzigen Informationen, die du hast, nur diese 4 Buchstaben sind, muss man Wahrscheinlichkeiten raten. Wenn du zb den Text komprimieren willst, ist deine Annahme super (weil du mit deinen Wahrscheinlichkeiten nie wieder auf einen anderen text anwenden wirst als deine 4 Buchstaben). Wenn du die Entropie dieser vier Buchstaben mit der Entropie von anderen Wörtern über dem gleichen Alphabet vergleichen willst, müsstest du entweder eine Statistik über alle diese Wörter machen, falls du alle diese Wörter schon von Anfang an kennst. Falls du keine anderen Wörter zu dieser Zeit kennst, wäre eine Gleichverteilung vielleicht eine anständige Annahme.

Danke für deine Anmerkungen - den Absatz kapiere ich aber nicht, wenn du willst, leg da noch etwas nach, ich würde das gern verstehen.