www.wikidata.de-de.nina.az

Entropieschätzung Das Themengebiet der befasst sich mit den unterschiedlichen Methoden für die statistische Schätzung de

Entropieschätzung

Das Themengebiet der Entropieschätzung befasst sich mit den unterschiedlichen Methoden für die statistische Schätzung der Shannon-Entropie auf der Basis von endlichen Stichproben.

Für die formale Berechnung der Shannon-Entropie ist gemäß Definition die Kenntnis der Wahrscheinlichkeiten der zugrunde liegenden Nachrichtenquelle notwendig. Jedoch sind in der Praxis diese Wahrscheinlichkeiten meistens unbekannt, und man ist darauf angewiesen, die Wahrscheinlichkeiten der Nachrichten aus einer vorgegebenen endlichen Stichprobe zu schätzen, um damit auf die Entropie der Gesamtheit zu schließen.

Aufgrund der naturgegebenen statistischen Schwankungen in endlichen Stichproben sind dabei systematische und unsystematische Abweichungen bei den Schätzungen zu erwarten. Bei dem gewöhnlichen Maximum-Likelihood-Schätzer für die Entropie werden die Wahrscheinlichkeiten , , in der Shannon-Entropie

durch die Maximum-Likelihood-Schätzer ersetzt. Erscheint im Falle von insgesamt Beobachtungen das Ereignis mit einer absoluten Häufigkeit von , so führt die Verwendung von zu dem in der Praxis häufig verwendeten Maximum-Likelihood-Schätzer für die Entropie

Dieser Schätzer ist aus statistischer Sicht besonders geeignet, wenn die Stichprobe sehr viel größer als die mögliche Anzahl der unterschiedlichen Ereignisse ist, d. h. gegeben ist. Andernfalls führt der obige Schätzer oft zu einer systematischen Unterschätzung der Entropie. Dieser Fehler wird besonders dann merklich, wenn der Umfang der Stichprobe nicht sehr viel größer als die Anzahl der unterschiedlichen Nachrichten der Quelle ist. In der Praxis ist jedoch letzteres oft von besonderem Interesse.

„Finite-Sample“-Korrekturen Bearbeiten

Es gibt eine Reihe von Ansätzen in der Literatur die sich damit befassen, den systematischen Fehler mit geeigneten Korrekturtermen sukzessive zu verringern. Dabei werden üblicherweise Taylor-Reihenentwicklung der Entropie vorgenommen. Für Korrekturen bis zur ersten Ordnung in ergibt sich beispielsweise der Schätzer

Der Korrekturterm wurde zuerst von Miller für die Untersuchung medizinischer Daten berücksichtigt. Weitere Anwendungen im Rahmen der Genforschung wurden beispielsweise später von Herzel vorgenommen. Die ersten Berechnungen von Korrekturtermen bis zur zweiten Ordnung wurden zuerst von Harris publiziert. Dabei stellt sich heraus, dass die Korrekturterme zweiter Ordnung nicht unabhängig von den zu schätzenden Wahrscheinlichkeiten sind. Zudem führt eine Substitution der Wahrscheinlichkeiten in diesen Termen durch die Maximum-Likelihood-Schätzer nicht zu Verbesserungen. Für praktische Zwecke ist das Ergebnis von Harris daher wenig geeignet.

Korrekturen höherer Ordnung Bearbeiten

Eine alternative Vorgehensweise, bei der ausschließlich beobachtbare Beiträge zu den Korrekturtermen höherer Ordnung beitragen, wurde zuerst von Peter Grassberger vorgeschlagen. Für die zu schätzenden Wahrscheinlichkeiten wird dabei die Bedingung vorausgesetzt, wobei die absoluten Häufigkeiten als unabhängige, Poisson-verteilte Zufallsvariable angesehen werden. Diese Annahmen sind insbesondere für die in der Praxis interessanten Beispiele meistens sehr gut erfüllt. Ausgangspunkt bei der Herleitung von Korrekturen höherer Ordnung ist dabei die Rényi-Entropie der Ordnung

Der formale Zusammenhang mit der Shannon-Entropie ergibt sich durch den Grenzübergang , d. h. . Es erscheint dann naheliegend, zunächst nach unverzerrten Schätzern für jeden der Summanden zu suchen. Für den Fall ganzzahliger Werte existieren solche unverzerrte Schätzer, d. h.

mit für . Für eine formale Bildung des Grenzwertes ist eine analytische Fortsetzung für beliebige reelle Werte von notwendig. Von Grassberger wurde dazu die -Funktion vorgeschlagen. Diese führt zwar nicht zu einem unverzerrten Schätzer für die Entropie, es ergibt sich jedoch ein asymptotisch unverzerrter Entropieschätzer,

der für endliche Stichproben in der Praxis zu Verbesserungen führt. Die Funktion bezeichnet dabei die sogenannte Digamma-Funktion. Für den interessanten Fall kleiner Wahrscheinlichkeiten ist der systematisch Fehler dieses Schätzers kleiner als bei dem Schätzer mit den von Miller vorgeschlagenen Korrekturen.

Systematische Korrekturen Bearbeiten

Auf ähnlich Weise lässt sich eine parametrisierte Schar von allgemeinen Entropieschätzern angeben, welche die obigen Schätzer fortsetzen bzw. asymptotisch repräsentieren. Anstatt einer Poisson-Verteilung wird dabei eine Binomialverteilung für die absoluten Häufigkeiten unterstellt. Weitere Restriktionen an die Wahrscheinlichkeiten werden dabei nicht gemacht. Als Entropieschätzer erhält man damit

wobei die reelle Variable unterschiedliche Entropieschätzer parametrisiert.

Beispiele

1. Im Fall verschwindet der Korrekturterm und man erhält den Entropieschätzer

Ein ähnlicher Schätzer wurde auch von Wolpert und Wolf im Rahmen der Bayes-Theorie diskutiert. Asymptotisch entspricht dieser Schätzer dem Miller-Schätzer.

2. Der Schätzer für reproduziert näherungsweise den Schätzer . Numerische Analysen ergeben, dass der Unterschied zwischen und vernachlässigbar gering ist. Der systematische Fehler von ist geringer als der systematische Fehler des Schätzers .

3. Der Fall entspricht asymptotisch einem weiteren von Grassberger hergeleiteten Entropieschätzer. Letzterer besitzt eine kleinere Verzerrung als der Miller-Schätzer und .

Systematischer Fehler (Verzerrung) Bearbeiten

Der Systematische Fehler eines Schätzers ist definiert als die erwartete Abweichung zwischen dem betrachteten Schätzer und der zu schätzenden Variablen. In dem hier vorliegenden Fall ergibt sich gemäß dieser Definition

Dieser Ausdruck ist explizit abhängig von den Wahrscheinlichkeiten und dem Parameter . Für jede Auswahl dieser Variablen ergibt sich ein charakteristischer Wert für den Schätzfehler, welcher sich wie folgt analytisch bestimmen lässt

Die Funktion auf der rechten Seite dieser Formel ist eine unvollständige Beta-Funktion und gehört zu der Klasse der sog. speziellen Funktionen. Für den unsystematischen Fehler lässt sich hingegen keine derartige Formel herleiten. Letzterer muss daher in der Regel numerisch bestimmt werden.

Einzelnachweise Bearbeiten

  1. C. E. Shannon, Bell Syst. Tech. 27 (1948) 379.
  2. C. E. Shannon and W. Weaver, 1949 The Mathematical Theory of Communication (Urbana, IL: University of Illinois Press.)
  3. G. Miller: Note on the bias of information estimates. In H. Quastler, ed., Information theory in psychology II-B, p. 95 (Free Press, Glencoe, IL, 1955).
  4. H. Herzel, Sys. Anal. Mod. Sim. 5, (1988) 435.
  5. B. Harris, Colloquia Math. Soc. Janos Bolya, p. 323 (1975)
  6. ↑ P. Grassberger, Phys. Lett. A 128, (1988) 369.
  7. ↑ T. Schürmann, J. Phys. A: Math. Gen. 37 (2004) L295, arxiv:cond-mat/0403192.
  8. D. H. Wolpert und D. R. Wolf, Phys. Rev. E 52, 6841 (1995).
  9. P. Grassberger, (2003) arxiv:physics/0307138.
  10. https://functions.wolfram.com/GammaBetaErf/Beta3/07/01/01/

Siehe auch Bearbeiten

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Das Themengebiet der Entropieschatzung befasst sich mit den unterschiedlichen Methoden fur die statistische Schatzung der Shannon Entropie auf der Basis von endlichen Stichproben Fur die formale Berechnung der Shannon Entropie ist gemass Definition die Kenntnis der Wahrscheinlichkeiten der zugrunde liegenden Nachrichtenquelle notwendig Jedoch sind in der Praxis diese Wahrscheinlichkeiten meistens unbekannt und man ist darauf angewiesen die Wahrscheinlichkeiten der Nachrichten aus einer vorgegebenen endlichen Stichprobe zu schatzen um damit auf die Entropie der Gesamtheit zu schliessen Aufgrund der naturgegebenen statistischen Schwankungen in endlichen Stichproben sind dabei systematische und unsystematische Abweichungen bei den Schatzungen zu erwarten Bei dem gewohnlichen Maximum Likelihood Schatzer fur die Entropie werden die Wahrscheinlichkeiten p i displaystyle p i i 1 2 K displaystyle i 1 2 ldots K in der Shannon Entropie 1 2 H i 1 K p i ln p i displaystyle H sum i 1 K p i ln p i dd durch die Maximum Likelihood Schatzer p i displaystyle hat p i ersetzt Erscheint im Falle von insgesamt N displaystyle N Beobachtungen das Ereignis i displaystyle i mit einer absoluten Haufigkeit von n i displaystyle n i so fuhrt die Verwendung von p i n i N displaystyle hat p i n i N zu dem in der Praxis haufig verwendeten Maximum Likelihood Schatzer fur die Entropie H i 1 K p i ln p i displaystyle hat H sum i 1 K hat p i ln hat p i dd Dieser Schatzer ist aus statistischer Sicht besonders geeignet wenn die Stichprobe sehr viel grosser als die mogliche Anzahl der unterschiedlichen Ereignisse ist d h N K displaystyle textstyle N gg K gegeben ist Andernfalls fuhrt der obige Schatzer oft zu einer systematischen Unterschatzung der Entropie Dieser Fehler wird besonders dann merklich wenn der Umfang N displaystyle N der Stichprobe nicht sehr viel grosser als die Anzahl K displaystyle K der unterschiedlichen Nachrichten der Quelle ist In der Praxis ist jedoch letzteres oft von besonderem Interesse Inhaltsverzeichnis 1 Finite Sample Korrekturen 2 Korrekturen hoherer Ordnung 3 Systematische Korrekturen 4 Systematischer Fehler Verzerrung 5 Einzelnachweise 6 Siehe auch Finite Sample Korrekturen BearbeitenEs gibt eine Reihe von Ansatzen in der Literatur die sich damit befassen den systematischen Fehler mit geeigneten Korrekturtermen sukzessive zu verringern Dabei werden ublicherweise Taylor Reihenentwicklung der Entropie vorgenommen Fur Korrekturen bis zur ersten Ordnung in N 1 displaystyle N 1 nbsp ergibt sich beispielsweise der Schatzer H M H K 1 2 N displaystyle hat H M hat H frac K 1 2N nbsp dd Der Korrekturterm wurde zuerst von Miller 3 fur die Untersuchung medizinischer Daten berucksichtigt Weitere Anwendungen im Rahmen der Genforschung wurden beispielsweise spater von Herzel 4 vorgenommen Die ersten Berechnungen von Korrekturtermen bis zur zweiten Ordnung wurden zuerst von Harris 5 publiziert Dabei stellt sich heraus dass die Korrekturterme zweiter Ordnung nicht unabhangig von den zu schatzenden Wahrscheinlichkeiten sind Zudem fuhrt eine Substitution der Wahrscheinlichkeiten in diesen Termen durch die Maximum Likelihood Schatzer nicht zu Verbesserungen Fur praktische Zwecke ist das Ergebnis von Harris daher wenig geeignet Korrekturen hoherer Ordnung BearbeitenEine alternative Vorgehensweise bei der ausschliesslich beobachtbare Beitrage zu den Korrekturtermen hoherer Ordnung beitragen wurde zuerst von Peter Grassberger 6 vorgeschlagen Fur die zu schatzenden Wahrscheinlichkeiten wird dabei die Bedingung p i 1 displaystyle p i ll 1 nbsp vorausgesetzt wobei die absoluten Haufigkeiten n i displaystyle textstyle n i nbsp als unabhangige Poisson verteilte Zufallsvariable angesehen werden Diese Annahmen sind insbesondere fur die in der Praxis interessanten Beispiele meistens sehr gut erfullt Ausgangspunkt bei der Herleitung von Korrekturen hoherer Ordnung ist dabei die Renyi Entropie der Ordnung q gt 0 displaystyle textstyle q gt 0 nbsp H q 1 1 q ln i 1 K p i q displaystyle H q frac 1 1 q ln sum i 1 K p i q nbsp dd Der formale Zusammenhang mit der Shannon Entropie ergibt sich durch den Grenzubergang q 1 displaystyle q to 1 nbsp d h H q H displaystyle H q to H nbsp Es erscheint dann naheliegend zunachst nach unverzerrten Schatzern fur jeden der Summanden p i q displaystyle p i q nbsp zu suchen Fur den Fall ganzzahliger Werte q 1 displaystyle q geq 1 nbsp existieren solche unverzerrte Schatzer d h p q 1 N q n n q n q displaystyle hat p q frac 1 N q frac n n q qquad qquad n geq q nbsp dd mit p q 0 displaystyle hat p q 0 nbsp fur n lt q displaystyle textstyle n lt q nbsp Fur eine formale Bildung des Grenzwertes q 1 displaystyle q to 1 nbsp ist eine analytische Fortsetzung fur beliebige reelle Werte von q gt 0 displaystyle q gt 0 nbsp notwendig Von Grassberger 6 wurde dazu die G displaystyle Gamma nbsp Funktion vorgeschlagen Diese fuhrt zwar nicht zu einem unverzerrten Schatzer fur die Entropie es ergibt sich jedoch ein asymptotisch unverzerrter Entropieschatzer H ps i 1 K n i N ln N ps n i 1 n i n i n i 1 displaystyle hat H psi sum i 1 K frac n i N left ln N psi n i frac 1 n i n i n i 1 right nbsp dd der fur endliche Stichproben in der Praxis zu Verbesserungen fuhrt Die Funktion ps x displaystyle psi x nbsp bezeichnet dabei die sogenannte Digamma Funktion Fur den interessanten Fall kleiner Wahrscheinlichkeiten p i 1 displaystyle p i ll 1 nbsp ist der systematisch Fehler dieses Schatzers kleiner als bei dem Schatzer mit den von Miller vorgeschlagenen Korrekturen Systematische Korrekturen BearbeitenAuf ahnlich Weise lasst sich eine parametrisierte Schar von allgemeinen Entropieschatzern angeben welche die obigen Schatzer fortsetzen bzw asymptotisch reprasentieren Anstatt einer Poisson Verteilung wird dabei eine Binomialverteilung fur die absoluten Haufigkeiten unterstellt Weitere Restriktionen an die Wahrscheinlichkeiten werden dabei nicht gemacht Als Entropieschatzer erhalt man damit 7 H 3 i 1 K n i N ps N ps n i 1 n i 0 1 3 1 t n i 1 1 t d t displaystyle hat H xi sum i 1 K frac n i N left psi N psi n i 1 n i cdot int 0 frac 1 xi 1 frac t n i 1 1 t mathrm d t right nbsp dd wobei die reelle Variable 3 gt 0 displaystyle xi gt 0 nbsp unterschiedliche Entropieschatzer parametrisiert Beispiele1 Im Fall 3 1 displaystyle xi 1 nbsp verschwindet der Korrekturterm und man erhalt den Entropieschatzer H 1 i 1 K n i N ps N ps n i displaystyle hat H 1 sum i 1 K frac n i N Big psi N psi n i Big nbsp dd Ein ahnlicher Schatzer wurde auch von Wolpert und Wolf 8 im Rahmen der Bayes Theorie diskutiert Asymptotisch entspricht dieser Schatzer dem Miller Schatzer 2 Der Schatzer fur 3 exp 1 2 0 6 displaystyle xi exp left tfrac 1 2 right approx 0 6 nbsp reproduziert naherungsweise den Schatzer H ps displaystyle hat H psi nbsp Numerische Analysen ergeben dass der Unterschied zwischen H ps displaystyle hat H psi nbsp und H 0 6 displaystyle hat H 0 6 nbsp vernachlassigbar gering ist Der systematische Fehler von H 0 6 displaystyle hat H 0 6 nbsp ist geringer als der systematische Fehler des Schatzers H ps displaystyle hat H psi nbsp 3 Der Fall 3 0 5 displaystyle xi 0 5 nbsp entspricht asymptotisch einem weiteren von Grassberger hergeleiteten Entropieschatzer 9 Letzterer besitzt eine kleinere Verzerrung als der Miller Schatzer und H ps displaystyle hat H psi nbsp Systematischer Fehler Verzerrung BearbeitenDer Systematische Fehler eines Schatzers ist definiert als die erwartete Abweichung zwischen dem betrachteten Schatzer und der zu schatzenden Variablen In dem hier vorliegenden Fall ergibt sich gemass dieser Definition Bias 3 p 1 p K E H 3 H displaystyle text Bias xi p 1 ldots p K E left hat H xi H right nbsp Dieser Ausdruck ist explizit abhangig von den Wahrscheinlichkeiten und dem Parameter 3 displaystyle xi nbsp Fur jede Auswahl dieser Variablen ergibt sich ein charakteristischer Wert fur den Schatzfehler welcher sich wie folgt analytisch bestimmen lasst 7 Bias 3 p 1 p K i 1 K p i B 1 p i 3 N 0 displaystyle text Bias xi p 1 ldots p K sum i 1 K p i cdot B 1 frac p i xi N 0 nbsp Die Funktion B z a b displaystyle text B z a b nbsp auf der rechten Seite dieser Formel ist eine unvollstandige Beta Funktion und gehort zu der Klasse der sog speziellen Funktionen 10 Fur den unsystematischen Fehler lasst sich hingegen keine derartige Formel herleiten Letzterer muss daher in der Regel numerisch bestimmt werden Einzelnachweise Bearbeiten C E Shannon Bell Syst Tech 27 1948 379 C E Shannon and W Weaver 1949 The Mathematical Theory of Communication Urbana IL University of Illinois Press G Miller Note on the bias of information estimates In H Quastler ed Information theory in psychology II B p 95 Free Press Glencoe IL 1955 H Herzel Sys Anal Mod Sim 5 1988 435 B Harris Colloquia Math Soc Janos Bolya p 323 1975 a b P Grassberger Phys Lett A 128 1988 369 a b T Schurmann J Phys A Math Gen 37 2004 L295 arxiv cond mat 0403192 D H Wolpert und D R Wolf Phys Rev E 52 6841 1995 P Grassberger 2003 arxiv physics 0307138 https functions wolfram com GammaBetaErf Beta3 07 01 01 Siehe auch BearbeitenBlockentropie Kullback Leibler Divergenz Abgerufen von https de wikipedia org w index php title Entropieschatzung amp oldid 227385611