Entropieschätzung

Das Themengebiet d​er Entropieschätzung befasst s​ich mit d​en unterschiedlichen Methoden für d​ie statistische Schätzung d​er Shannon-Entropie a​uf der Basis v​on 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 ${\displaystyle p_{i}}$, ${\displaystyle i=1,2,\ldots ,K}$, in der Shannon-Entropie[1][2]

${\displaystyle H=-\sum _{i=1}^{K}p_{i}\ln p_{i}}$,

durch die Maximum-Likelihood-Schätzer ${\displaystyle {\hat {p}}_{i}}$ ersetzt. Erscheint im Falle von insgesamt ${\displaystyle N}$ Beobachtungen das Ereignis ${\displaystyle i}$ mit einer absoluten Häufigkeit von ${\displaystyle n_{i}}$, so führt die Verwendung von ${\displaystyle {\hat {p}}_{i}=n_{i}/N}$ zu dem in der Praxis häufig verwendeten Maximum-Likelihood-Schätzer für die Entropie

${\displaystyle {\hat {H}}=-\sum _{i=1}^{K}{\hat {p}}_{i}\ln {\hat {p}}_{i}.}$

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. ${\displaystyle \textstyle N\gg K}$ 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 ${\displaystyle N}$ der Stichprobe nicht sehr viel größer als die Anzahl ${\displaystyle K}$ der unterschiedlichen Nachrichten der Quelle ist. In der Praxis ist jedoch letzteres oft von besonderem Interesse.

„Finite-Sample“-Korrekturen

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 ${\displaystyle N^{-1}}$ ergibt sich beispielsweise der Schätzer

${\displaystyle {\hat {H}}_{M}={\hat {H}}+{\frac {K-1}{2N}}}$

Der Korrekturterm wurde zuerst von Miller[3] für die Untersuchung medizinischer Daten berücksichtigt. Weitere Anwendungen im Rahmen der Genforschung wurden beispielsweise später 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 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

Eine alternative Vorgehensweise, bei der ausschließlich beobachtbare Beiträge zu den Korrekturtermen höherer Ordnung beitragen, wurde zuerst von Peter Grassberger[6] vorgeschlagen. Für die zu schätzenden Wahrscheinlichkeiten wird dabei die Bedingung ${\displaystyle p_{i}\ll 1}$ vorausgesetzt, wobei die absoluten Häufigkeiten ${\displaystyle \textstyle n_{i}}$ 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 ${\displaystyle \textstyle q>0}$

${\displaystyle H(q)={\frac {1}{1-q}}\ln \sum _{i=1}^{K}p_{i}^{q}}$

Der formale Zusammenhang mit der Shannon-Entropie ergibt sich durch den Grenzübergang ${\displaystyle q\to 1}$, d. h. ${\displaystyle H(q)\to H}$. Es erscheint dann naheliegend, zunächst nach unverzerrten Schätzern für jeden der Summanden ${\displaystyle p_{i}^{q}}$ zu suchen. Für den Fall ganzzahliger Werte ${\displaystyle q\geq 1}$ existieren solche unverzerrte Schätzer, d. h.

${\displaystyle {\hat {p^{q}}}={\frac {1}{N^{q}}}{\frac {n!}{(n-q)!}}\qquad \qquad n\geq q}$

mit ${\displaystyle {\hat {p^{q}}}=0}$ für ${\displaystyle \textstyle n<q}$. Für eine formale Bildung des Grenzwertes ${\displaystyle q\to 1}$ ist eine analytische Fortsetzung für beliebige reelle Werte von ${\displaystyle q>0}$ notwendig. Von Grassberger[6] wurde dazu die ${\displaystyle \Gamma }$-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,

${\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),}$

der für endliche Stichproben in der Praxis zu Verbesserungen führt. Die Funktion ${\displaystyle \psi (x)}$ bezeichnet dabei die sogenannte Digamma-Funktion. Für den interessanten Fall kleiner Wahrscheinlichkeiten ${\displaystyle p_{i}\ll 1}$ ist der systematisch Fehler dieses Schätzers kleiner als bei dem Schätzer mit den von Miller vorgeschlagenen Korrekturen.

Systematische Korrekturen

Auf ähnlich Weise lässt s​ich eine parametrisierte Schar v​on allgemeinen Entropieschätzern angeben, welche d​ie obigen Schätzer fortsetzen bzw. asymptotisch repräsentieren. Anstatt e​iner Poisson-Verteilung w​ird dabei e​ine Binomialverteilung für d​ie absoluten Häufigkeiten unterstellt. Weitere Restriktionen a​n die Wahrscheinlichkeiten werden d​abei nicht gemacht. Als Entropieschätzer erhält m​an damit[7]

${\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)}$,

wobei die reelle Variable ${\displaystyle \xi >0}$ unterschiedliche Entropieschätzer parametrisiert.

Beispiele

1. Im Fall ${\displaystyle \xi =1}$ verschwindet der Korrekturterm und man erhält den Entropieschätzer

${\displaystyle {\hat {H}}^{(1)}=\sum _{i=1}^{K}{\frac {n_{i}}{N}}{\Big (}\psi (N)-\psi (n_{i}){\Big )}.}$

Ein ähnlicher Schätzer w​urde auch v​on Wolpert u​nd Wolf[8] i​m Rahmen d​er Bayes-Theorie diskutiert. Asymptotisch entspricht dieser Schätzer d​em Miller-Schätzer.

2. Der Schätzer für ${\displaystyle \xi =\exp \left(-{\tfrac {1}{2}}\right)\approx 0{,}6}$ reproduziert näherungsweise den Schätzer ${\displaystyle {\hat {H}}_{\psi }}$. Numerische Analysen ergeben, dass der Unterschied zwischen ${\displaystyle {\hat {H}}_{\psi }}$ und ${\displaystyle {\hat {H}}^{(0{,}6)}}$ vernachlässigbar gering ist. Der systematische Fehler von ${\displaystyle {\hat {H}}^{(0{,}6)}}$ ist geringer als der systematische Fehler des Schätzers ${\displaystyle {\hat {H}}_{\psi }}$.

3. Der Fall ${\displaystyle \xi =0{,}5}$ entspricht asymptotisch einem weiteren von Grassberger hergeleiteten Entropieschätzer.[9] Letzterer besitzt eine kleinere Verzerrung als der Miller-Schätzer und ${\displaystyle {\hat {H}}_{\psi }}$.

Systematischer Fehler (Verzerrung)

Der Systematische Fehler e​ines Schätzers i​st definiert a​ls die erwartete Abweichung zwischen d​em betrachteten Schätzer u​nd der z​u schätzenden Variablen. In d​em hier vorliegenden Fall ergibt s​ich gemäß dieser Definition

${\displaystyle {\text{Bias}}(\xi ;p_{1},\ldots ,p_{K})=E\left[{\hat {H}}^{(\xi )}-H\right]}$

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

${\displaystyle {\text{Bias}}(\xi ;p_{1},\ldots ,p_{K})=-\sum _{i=1}^{K}p_{i}\cdot B_{1-{\frac {p_{i}}{\xi }}}(N,0)}$

Die Funktion ${\displaystyle {\text{B}}_{z}(a,b)}$ auf der rechten Seite dieser Formel ist eine unvollständige Beta-Funktion und gehört zu der Klasse der sog. speziellen Funktionen.[10] Für den unsystematischen Fehler lässt sich hingegen keine derartige Formel herleiten. Letzterer muss daher in der Regel numerisch bestimmt werden.

Referenzen

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

• Blockentropie
• Kullback-Leibler-Divergenz