Blockentropie

Die Übertragung von Symbolfolgen oder Zeichenketten aus einem endlichen Alphabet ergeben sich in fast allen gängigen wissenschaftlichen Disziplinen, d. h. alle geschriebenen Texte, Programm-Code, DNA-Sequenzen, digital gewandelte Daten von Musik oder Bildern bei der Informationsübertragung sowie eine große Anzahl von Anwendungen aus der Mathematik oder Physik.

Wird eine solche Symbolfolge in aufeinanderfolgende Teilblöcke, Wörter oder Subsequenzen aufgeteilt, so kann man diese Teilblöcke formal als Nachricht auffassen. Bei dieser Aufteilung wird im Allgemeinen keine Rücksicht auf syntaktische, semantische oder sonstige Strukturen genommen. Beispielsweise ist das erste Wort der Länge 10 in dieser Einleitung "Die Übertr", das zweite Wort gleicher Länge ist "agung von ".

Jedem dieser unterschiedlichen Teilblöcke entspricht eine Wahrscheinlichkeit, mit welcher dieser in der jeweils vorliegenden Stichprobe auftritt. Die Blockentropie ist definiert als die Entropie, welche den Wahrscheinlichkeiten der Teilblöcke entspricht.

Blockentropien

Für eine formale Beschreibung der Blockentropien im Rahmen der Theorie von Shannon^[1][2] betrachtet man eine unendliche Folge $s_{\scriptstyle 1},s_{\scriptstyle 2},...$ von Symbolen (Buchstaben, Zeichen) aus einem endlichen Alphabet {0,1,...,d − 1} der Mächtigkeit d. Es wird dabei vorausgesetzt, dass diese Symbole Realisierungen eines stochastischen Prozesses $S_{\scriptstyle 1},S_{\scriptstyle 2},...$ sind mit den Wahrscheinlichkeiten $p_t(s_{\scriptstyle 1},s_{\scriptstyle 2},...,s_{\scriptstyle n})=\text{prob}(S_{\scriptstyle t+1}=s_{\scriptstyle 1},...,S_{\scriptstyle t+n}=s_n)$ für das Auftreten des Teilstrings $s_{\scriptstyle 1},s_{\scriptstyle 2},...,s_{\scriptstyle n}$. Üblicherweise werden diese Wahrscheinlichkeiten als stationär angenommen, und man lässt in solchen Fällen den Zeitindex t weg. Die sogenannten Blockentropien der Ordnung n werden von Shannon formal durch

$H_n=-\sum_{s_1,...,s_n} p(s_1,s_2,...,s_n)\log p(s_1,s_2,...,s_n)$

definiert. Im Rahmen der Kommunikationstheorie von Shannon ist H_n gleich der mittleren Anzahl von Fragen die mindestens benötigt werden um bei binären Antworten den Teilblock s₁,...,s_n zu erfahren. Dabei wird unterstellt, dass dem Fragenden die Werte für die Wahrscheinlichkeiten der Teilblöcke bekannt sind und das die Fragestrategie auf optimale Weise vorgenommen wird (vgl. Huffman-Kodierung). In diesem Sinne spricht man auch von mittlerer Kodierungslänge der Teilblöcke.

Entropie einer Informationsquelle

Betrachtet man die Definition der Blockentropie, so stellt sich in diesem Zusammenhang die Frage nach dem Grenzwert, wenn man die Blocklänge der Teilwörter formal gegen unendlich streben lässt. Für Quellen, deren Wahrscheinlichkeiten sich nicht im Laufe der Zeit ändern (stationäre Quellen) kann allgemein bewiesen werden, dass der folgende Grenzwert existiert^[3]

$h = \lim_{n\to\infty} \frac{H_n}{n}$.

Diese Zahl ist die mittlere Kodierungslänge pro Symbol oder auch Shannon-Entropie der Informationsquelle.^[2]

Differentielle Entropie

Eine alternative Bestimmung von h, welche ebenfalls auf der Blockentropie basiert, ist durch die differentiellen Entropien

$h_n = H_{n+1}-H_n=-\sum_{s_1,...s_{n+1}} p(s_1,...,s_{n+1})\log p(s_{n+1}|s_1,s_2,...,s_n)$,

gegeben. Sie geben die mittleren Informationsgehalt des (n + 1)-ten Symbols an, unter der Voraussetzung, dass die vorhergehenden n Symbole $s_{\scriptstyle 1},s_{\scriptstyle 2},...,s_{\scriptstyle n}$ jeweils bekannt sind. Hierbei sind $p(s_{\scriptstyle n+1}|s_{\scriptstyle 1},s_{\scriptstyle 2},...,s_{\scriptstyle n})$ die Wahrscheinlichkeiten dafür, dass $S_{n+1}=s_{\scriptstyle n+1}$ eintritt, gegeben dass die vorhergehenden Symbole $s_{\scriptstyle 1},s_{\scriptstyle 2},...,s_{\scriptstyle n}$ vorliegen.

Konvergenzverhalten

Die Folgen h_n und H_n / n streben jeweils monoton fallend gegen den Grenzwert h, d.h. sie sind obere Schranke der Entropie der Nachrichtenquelle. Genaue Aussagen über das Konvergenzverhalten dieser Folgen können im Allgemeinen nur für sehr spezielle Systeme (Quellen) bewiesen werden.

Beispiele

1. Bernoulli-Prozesse: Für sog. Bernoulli-Prozesse faktorisieren die Wahrscheinlichkeiten, d.h.

$p(s_1,s_2,...,s_n)=p(s_1)\,p(s_2)...p(s_n).$

Somit ist die Blockentropie n-ter Ordnung das n-fache von H₁, d.h. H_n = nH₁ und der Grenzwert h = H₁ ist bereits für n = 1 erreicht.

2. Markov-Prozesse: Bei einer speziellen Form von Nachrichtenquellen mit Gedächtnis, d.h. Markov-Quellen mit der Ordnung m, wächst die Blockentropie gemäß

H_n = H_m + (n − m)(H_{m + 1} − H_m)

für $n\geq m$ an. Die Entropie der Markov-Quelle ist demnach h = H_{m + 1} − H_m.

3. Für periodische Symbolfolgen mit der Periodenlänge q ergeben weitere Symbole keine neue Information. In diesem Fall ist

H_n = H_q,

für $n\geq q$. Daher verschwindet die Entropie, d.h. h = 0, - die Nachrichten sind vollständig determiniert.

4. Chaotische Prozesse: Nicht trivial ist beispielsweise die Konvergenz der Blockentropie beim Übergang von periodischem Verhalten zu chaotischem Verhalten in nichtlinearen dynamischen Systemen. Bei der Logistischen Abbildung tritt ein solcher Übergang am sogenannten Feigenbaumpunkt ein. Aufgrund der Struktur der Periodenverdopplung an diesem Punkt ergibt sich für die Blockentropie der Ausdruck

$H_n=\log_2\frac{3n}{2}$

für alle n = 2^k und k = 1,2,..., d.h. die Entropie pro Symbol konvergiert $\propto\log(n)/n$ gegen Null.^[4] Die differentielle Entropie konvergiert demnach $\propto 1/n$ gegen Null. Weitere Beispiele für derartiges Konvergenzverhalten ergibt sich beispielsweise für die sog. Rabbit-Sequenz, deren Symboldynamik mit der Kreis-Abbildung im Zusammenhang steht.^[5]

Statistische Schätzung der Blockentropie

Zur numerischen Schätzung der Entropie aus endlichen Stichproben von Symbolfolgen der Länge N werden gewöhnlich die Wahrscheinlichkeiten $p(s_{\scriptstyle 1},s_{\scriptstyle 2},...,s_{\scriptstyle n})$ für eine feste Blocklänge n durch den Likelihood-Schätzer

$\hat{p}(s_1,...,s_n)=\frac{n_{s_1,...,s_n}}{N}$

bestimmt. Die Häufigkeiten $n_{s_1,...,s_n}$ geben an, wie oft das Wort $s_{\scriptstyle 1},s_{\scriptstyle 2},...,s_{\scriptstyle n}$ in der Stichprobe vorkommt. Der Schätzwert $\hat{H}_n$ für die Blockentropie H_n wird dann durch einsetzen der relativen Häufigkeiten vorgenommen. Schließlich erhält man einen Entropieschätzer für h durch die Grenzwertbildung $\lim_{n\to\infty}{\hat H_n}/n$. In numerischen Berechnungen, wenn die der Stichprobe nicht hinreichend umfangreich ist, dann wird eine zuverlässige Schätzung der Wahrscheinlichkeiten $p(s_{\scriptstyle 1},s_{\scriptstyle 2},...,s_{\scriptstyle n})$ nur sehr schwer möglich. Das kommt daher, dass die Anzahl der möglichen Blöcke mit der Länge n exponentiell zunimmt und damit auch die notwendige Größe N der Stichprobe, die zu einer hinreichend zuverlässigen Bestimmung der Wahrscheinlichkeiten $p(s_{\scriptstyle 1},s_{\scriptstyle 2},...,s_{\scriptstyle n})$ benötigt wird. Die Bestimmung der Entropie für endliche Stichproben wird in der Theorie der Entropieschätzung untersucht.^{[6][7][8][9][10]}

Referenzen

1. ↑ C. E. Shannon, Bell Syst. Tech. 27 (1948) 379.
2. ↑ ^{a b} C. E. Shannon and W. Weaver, 1949 The Mathematical Theory of Communication (Urbana, IL: University of Illinois Press.)
3. ↑ A. I. Khinchin, 1957 Mathematical Foundations of Informationtheory (Dover, 1957).
4. ↑ P. Grassberger, Int. J. Theor. Phys. 25 (1986) 907.
5. ↑ T. Gramss, Phys. Ref. E 50 (1994) 2612.
6. ↑ B. Harris, 1975 The statistical estimation of entropy in the non-parametric case, Topics in Information Theory, ed. Csiszar (Amsterdam: North-Holland) pp. 323-55.
7. ↑ H. Herzel, Syst. Anal. Modelling Simul. 5 (1988) 435.
8. ↑ P. Grassberger, Phys. Lett.A 128 (1988) 369
9. ↑ T. Schürmann und P. Grassberger, CHAOS 6 (1996) 414-427. Online
10. ↑ L. Paninski, Neural Comput. 15 (2003) 1191

Siehe auch

• Entropieschätzung
• Symbolische Dynamik

Weblinks

• Entropy Rate of a Source (englisch)
• Selbstorganisation und Information, Frank Schweitzer, Institut für Physik der Humboldt-Universität Berlin (pdf; 713 kB)