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 likelihood Schätzer für die Entropie werden die Wahrscheinlichkeiten p_i, i = 1,2,...,K, in der Shannon-Entropie^[1][2]

$H=-\sum_{i=1}^K p_i \ln p_i$,

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

$\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. $\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 N der Stichprobe nicht sehr viel größer als die Anzahl 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 N ^{− 1} ergibt sich beispielsweise der Schätzer

$\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 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 Grassberger^[6] vorgeschlagen. Für die zu schätzenden Wahrscheinlichkeiten wird dabei die Bedingung $p_i\ll 1$ vorausgesetzt, wobei die absoluten Häufigkeiten $\textstyle n_i$ als unabhängige, Poissonverteilte 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 Renyi-Entropie der Ordnung $\textstyle q>0$

$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 $q\to 1$, d.h. $H(q)\to H$. Es erscheint dann naheliegend, zunächst nach unverzerrten Schätzern für jeden der Summanden $p_i^q$ zu suchen. Für den Fall ganzzahliger Werte $q\geq 1$ existieren solche unverzerrte Schätzer, d.h.

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

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

$\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 ψ(x) bezeichnet dabei die sogenannte Digamma-Funktion. Für den interessanten Fall kleiner Wahrscheinlichkeiten $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 sich eine parameterisierte Schar von allgemeinen Entropieschätzern angeben, welche die obigen Schätzer fortsetzen bzw. asymptotisch repräsentieren. Anstatt einer Poissonverteilung 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^[7]

$\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 dt \right)$,

wobei die reelle Variable ξ > 0 unterschiedliche Entropieschätzer parameterisiert.

Beispiele

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

$\hat{H}^{(1)}=\sum_{i=1}^K\frac{n_i}{N} \Big(\psi(N) -\psi(n_i)\Big).$

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

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

3. Der Fall ξ = 0,5 entspricht asymptotisch einem weiteren von Grassberger hergeleiteten Entropieschätzer.^[9] Letzterer besitzt einen kleineren Bias als der Miller-Schätzer und $\hat{H}_\psi$.

Systematischer Fehler (Bias)

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

$\text{Bias}(\xi;p_1,...,p_K)=E\left[ \hat{H}^{(\xi)}-H \right]$

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^[7]

$\text{Bias}(\xi;p_1,...,p_K) = -\sum_{i=1}^K p_i \cdot B_{1-\frac{p_i}{\xi}}(N,0)$

Die Funktion 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 [3]. 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. ↑ ^{a b} P. Grassberger, Phys. Lett. A 128, (1988) 369.
7. ↑ ^{a b} T. Schürmann, J. Phys. A: Math. Gen. 37 (2004) L295 [1].
8. ↑ D. H. Wolpert und D. R. Wolf, Phys. Rev. E 52, 6841 (1995).
9. ↑ P. Grassberger, arXiv:physics/0307138v2 (2003)[2].

Siehe auch

• Blockentropie
• Kullback-Leibler-Divergenz