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.

Inhaltsverzeichnis

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 Hn gleich der mittleren Anzahl von Fragen die mindestens benötigt werden um bei binären Antworten den Teilblock s1,...,sn 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 hn und Hn / 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 H1, d.h. Hn = nH1 und der Grenzwert h = H1 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äß

Hn = Hm + (nm)(Hm + 1Hm)

für n\geq m an. Die Entropie der Markov-Quelle ist demnach h = Hm + 1Hm.

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

Hn = Hq,

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 = 2k 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 Hn 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

Weblinks


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Verbundentropie — 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… …   Deutsch Wikipedia

  • Bedingte Entropie — In der Informationstheorie ist die bedingte Entropie ein Maß für die „Ungewissheit“ über den Wert einer Zufallsvariablen X, welche verbleibt, nachdem das Ergebnis einer anderen Zufallsvariable Y bekannt wird. Die bedingte Entropie wird H(X | Y)… …   Deutsch Wikipedia

  • Informationsdichte — Entropie ist ein Maß für den mittleren Informationsgehalt oder auch Informationsdichte eines Zeichensystems. Der Begriff in der Informationstheorie ist in Analogie zur Entropie in der Thermodynamik und Statistischen Mechanik benannt. Beide… …   Deutsch Wikipedia

  • Informationsentropie — Entropie ist ein Maß für den mittleren Informationsgehalt oder auch Informationsdichte eines Zeichensystems. Der Begriff in der Informationstheorie ist in Analogie zur Entropie in der Thermodynamik und Statistischen Mechanik benannt. Beide… …   Deutsch Wikipedia

  • Maximale Entropie — Entropie ist ein Maß für den mittleren Informationsgehalt oder auch Informationsdichte eines Zeichensystems. Der Begriff in der Informationstheorie ist in Analogie zur Entropie in der Thermodynamik und Statistischen Mechanik benannt. Beide… …   Deutsch Wikipedia

  • Maximalentropie — Entropie ist ein Maß für den mittleren Informationsgehalt oder auch Informationsdichte eines Zeichensystems. Der Begriff in der Informationstheorie ist in Analogie zur Entropie in der Thermodynamik und Statistischen Mechanik benannt. Beide… …   Deutsch Wikipedia

  • Shannon-Entropie — Entropie ist ein Maß für den mittleren Informationsgehalt oder auch Informationsdichte eines Zeichensystems. Der Begriff in der Informationstheorie ist in Analogie zur Entropie in der Thermodynamik und Statistischen Mechanik benannt. Beide… …   Deutsch Wikipedia

  • Shannonentropie — Entropie ist ein Maß für den mittleren Informationsgehalt oder auch Informationsdichte eines Zeichensystems. Der Begriff in der Informationstheorie ist in Analogie zur Entropie in der Thermodynamik und Statistischen Mechanik benannt. Beide… …   Deutsch Wikipedia

  • Entropie (Informationstheorie) — Entropie ist ein Maß für den mittleren Informationsgehalt oder auch Informationsdichte eines Zeichensystems. Der Begriff in der Informationstheorie ist in Analogie zur Entropie in der Thermodynamik und Statistischen Mechanik benannt. Das… …   Deutsch Wikipedia

  • Entropie (Physik) — Dieser Artikel wurde aufgrund von inhaltlichen Mängeln auf der Qualitätssicherungsseite des Portals Physik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Physik auf ein akzeptables Niveau zu bringen. Dabei werden… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”