„Verbundentropie“ – Versionsunterschied

Versionsgeschichte interaktiv durchsuchen

[ungesichtete Version]

[gesichtete Version]

← Zum vorherigen Versionsunterschied

Inhalt gelöscht Inhalt hinzugefügt

VisuellWikitext

Inline

Aktuelle Version vom 17. Mai 2022, 10:27 Uhr

Die Verbundentropie ist ein Maß für den mittleren Informationsgehalt mehrerer Nachrichtenquellen.

Definition

Die Verbundentropie für zwei Quellen ist folgendermaßen definiert:^[1]

H(XY):=-\sum _{y\in Y}\sum _{x\in X}Pr\{X=x,Y=y\}\log _{2}(Pr\{X=x,Y=y\})\quad {\Big [}{\frac {\text{ bit }}{\text{Symbolpaar}}}{\Big ]}

Hierbei sind $x$ und $y$ jeweils einzelne Symbole aus den Quellenalphabeten $X$ und $Y$ .

Im Spezialfall der statistischen Unabhängigkeit der Quellen gilt

Pr\{X=x_{i},Y=y_{j}\}=Pr\{X=x_{i}\}\cdot Pr\{y=y_{j}\}

und somit

H(XY)=H(X)+H(Y)

.

Für mehr als zwei Quellen ergibt sich:

H(X_{1},\dots ,X_{n})=-\sum _{x_{1}}\dots \sum _{x_{n}}Pr\{x_{1},\dots ,x_{n}\}\log _{2}(Pr\{x_{1},\dots ,x_{n}\})

Siehe auch

Literatur

Martin Werner: Information und Codierung. Grundlagen und Anwendungen, 2. Auflage, Vieweg + Teubner Verlag, Wiesbaden 2008, ISBN 978-3-8348-0232-3.
Peter Bocker: Datenübertragung. Band I – Grundlagen. Springer Verlag, Berlin / Heidelberg 1976, ISBN 978-3-662-06499-3.

Weblinks

Informationstheorie (abgerufen am 8. März 2018)
Kodierungs- und Informationstheorie (abgerufen am 8. März 2018)
Entropie (abgerufen am 8. März 2018)
Information und Kommunikation (abgerufen am 8. März 2018)

Einzelnachweise

↑ T. H. Cover, J. A. Thomas, Elements of Information Theory, S. 16 f, 2nd Edition, 2006, Wiley Interscience, ISBN 978-0-471-24195-9

[cover-1] T. H. Cover, J. A. Thomas, Elements of Information Theory, S. 16 f, 2nd Edition, 2006, Wiley Interscience, ISBN 978-0-471-24195-9

[1]

@@ Zeile 1: / Zeile 1: @@
-Die '''Verbundentropie''' bzw. '''Blockentropie''' ist die Verallgemeinerung der [[Shannonentropie]] für eine [[multivariat]]e [[Zufallsvariable]].
+Die '''Verbundentropie''' ist ein Maß für den [[Entropie (Informationstheorie)|mittleren Informationsgehalt]] mehrerer Nachrichtenquellen.
+== Definition ==
-Sei ''X'' eine multivariate Zufallsvariable (ein Zufallsvektor) Länge ''k'' und  '''''x''''' eine Realisierung von ''X'' über einer Symbolmenge ''Z'' (beispielsweise eine [[DNA]]-Sequenz mit ''Z={A,G,C,T}''). Sei weiterhin ''I'' eine Information (z.B. ein Text) der Länge n>k über der gleichen Symbolmenge ''Z''. Betrachtet man nun eine Realisierung '''''x''''' als eine Folge von Symbolen x<sub>j</sub> aus ''z'' (genannt '''Block'''), dann gibt die [[Verbundwahrscheinlichkeit]]
-:<math>p_k(\mathbf{x}) = p(x_1\,x_2..x_k) = p(x_1)\cdot p(x_2..x_k|x_1)</math>
-an, wie groß die Wahrscheinlichkeit ist, dass ein bestimmter ''k''-Zeichen-Block in ''I'' vorkommt. Die Menge aller möglichen Realisierungen bzw. Blöcke sei ''[X]<sub>k</sub>''. Man kann darüber die '''Blockentropie''' definieren:
- <math>H_k(\mathbf{x})=-\sum_{\mathbf{x} \in [X]_k} p_k(\mathbf{x}) \log p_k(\mathbf{x})</math>
-Die Menge ''[X]<sub>k</sub>'' wird in den meisten Fällen auch Realisierungen enthalten, die nicht in ''I'' vorkommen, also ''p<sub>k</sub>''('''''x''''')=0. Die Anzahl aller möglichen Realisierungen |''[X]<sub>k</sub>''| ist gemäß [[Kombinatorik]] gegeben durch:
-:<math>|[X]_k| = |Z|^k</math>
-Eine allgemeinere Formulierung der '''Verbundentropie''' ''H(X<sub>1</sub>,X<sub>2</sub>)'' für zwei Zufallsvariablen ''X<sub>1</sub>'' und ''X<sub>2</sub>'' ist gegeben durch
-:<math>H(X_1,X_2) = H(X_1) + H(X_2|X_1)</math>
-die Summe aus der '''Entropie''' von ''X<sub>1</sub>'' und der '''bedingten Entropie''' von ''X<sub>2</sub>'' unter gegebenem ''X<sub>1</sub>''. Sind ''X<sub>1</sub>'' und ''X<sub>2</sub>'' unabhängig, dann gilt (äquivalent zur [[Bedingte Wahrscheinlichkeit|bedingten Wahrscheinlichkeit]]):
-:<math>H(X_1,X_2) = H(X_1) + H(X_2)</math>
-Die '''bedingte Entropie''' wird im Folgenden erläutert.
+Die Verbundentropie für zwei Quellen ist folgendermaßen definiert:<ref name="cover" />
-== Bedingte Entropie ==
-Die ''bedingte Entropie'' von zwei Zufallsvariablen ''X'' und ''Y'' ist die Unsicherheit über ''Y'', die verbleibt, wenn ''X'' bereits bekannt ist. Sind ''X'' und ''Y'' voneinander ''unabhängig'', dann bleibt die Entropie von ''Y'' vollständig erhalten. Sind ''X'' und ''Y'' aber voneinander ''abhängig'', dann kann die bedingte Entropie kleiner sein als im ''unabhängigen'' Fall.
+:<math>H(XY) := - \sum_{y \in Y} \sum_{x \in X} Pr \{ X = x, Y = y \} \log_2 ( Pr \{ X = x, Y = y \} ) \quad \Big[ \frac{\text{ bit }}{\text{Symbolpaar}} \Big]</math>
-Formal ist die bedingte Entropie ''H(X|Y)'' definiert durch:
-:<math>\begin{matrix}
-H(Y|X) &=& \sum_{x \in X}{p(x) \cdot H(Y|X=x)}\\
-\\
-&=& \sum_{x \in X}{p(x) \cdot \left(-\sum_{y \in Y}{p(y|x) \cdot \log{p(y|x)}}\right)}\\
-\\
-&=& \sum_{x \in X}{p(x) \cdot \left(-\sum_{y \in Y}{\frac{p(yx)}{p(x)} \cdot \log{p(y|x)}}\right)}\\
-\\
-&=& \sum_{x \in X}{\sum_{y \in Y}{p(yx) \cdot \log{p(y|x)}}}\\
-\end{matrix}</math>
+Hierbei sind <math>x</math> und <math>y</math> jeweils einzelne Symbole aus den Quellenalphabeten <math>X</math> und <math>Y</math>.
-Für den Fall, dass ''X'' und ''Y'' ''unabhängig'' sind, ergibt sich:
-:<math>H(Y|X) = H(Y)</math>
+Im Spezialfall der statistischen Unabhängigkeit der Quellen gilt
+:<math>Pr\{ X = x_i, Y = y_j \} = Pr\{X = x_i\} \cdot Pr\{y = y_j\}</math>
-Übertragen auf eine multivariate Zufallsvariable ''X'' der Länge ''k'' (siehe oben), als Darstellung für einen k-Block von Symbolen ''(x<sub>1</sub>,..,x<sub>k</sub>)'', lässt sich die '''bedingte Entropie''' ''h<sub>k</sub>'' definieren als die Unsicherheit eines Symbols ''x<sub>k+1</sub>'' (nach einem bestimmten vorgegebenen ''k''-Block):
-:<math>h_k := H_{k+1} - H_k \mbox{ , mit } h_0 := H_1</math>
-wobei ''H<sub>k+1</sub>'' bzw. ''H<sub>k</sub>'' die '''Blockentropie''' ist.
+und somit
-=== Der zweidimensionale Fall ===
-Wenn das Auftreten eines Zeichens ''x<sub>i</sub>'' nur vom vorherigen Zeichen ''x<sub>j</sub>'' abhängt (wie etwa in der "101010..."-kette) erhält man aus
-:<math>
-H(X,Y) = \sum_i \sum_j p(x_i,y_j) \log p(x_i,y_j)
-</math>
-und
-:<math>
-p(x_i,y_j) = p(x_i) p(y_j|x_i)
-</math>
-den Ausdruck
- <math>
- \begin{matrix}
- H(X,Y) &=& \sum_i \sum_j p(x_i) p(y_j|x_i) \log_2(p(x_i) p(y_j|x_i)) \\
- &=& - \sum_i p(x_i) \log_2 p(x_i) \sum_j p(y_j|x_i) - \sum_i \sum_j p(x_i,y_j) \log_2 p(y_j|x_i)\\
- &=& H(X) + H(Y|X)
- \end{matrix}
-</math>
-wobei ''x<sub>i</sub>'' den Zustand, d.h. die Folge der vorhergehenden Symbole, bezeichnet und p(''y<sub>j</sub>''|''x<sub>i</sub>'') ist die [[bedingte Wahrscheinlichkeit]] von ''y<sub>j</sub>'' gegeben ''x<sub>i</sub>''. Die [[Verbundwahrscheinlichkeit]] von ''x<sub>i</sub>'' und ''y<sub>j</sub>'', p(''x<sub>i</sub>'',''y<sub>j</sub>'') ist wiederum die Wahrscheinlichkeit des gemeinsamen Auftretens von ''x<sub>i</sub>'' und ''y<sub>j</sub>''.
+:<math>H(XY) = H(X) + H(Y)</math>.
-Es lautet also hier ''h<sub>1</sub>'':
+Für mehr als zwei Quellen ergibt sich:
-:<math>
- h_1 = H_2 - H_1 = H(X) + H(Y|X) - H(X) = H(Y|X)  = - \sum_i p(x_i) \sum_j p(y_j|x_i) \log_2 p(y_j|x_i)
-</math>
+:<math>H(X_1, \dots, X_n) = - \sum_{x_1} \dots \sum_{x_n} Pr\{x_1, \dots, x_n\} \log_2( Pr\{x_1, \dots, x_n\} )</math>
-== Quellentropie ==
-Schließlich ist zu bemerken, dass die beiden vorgenannten Definitionen im [[Grenzübergang]] gleichwertig sind; man erhält einen Ausdruck, der die Entropie pro Symbol unabhängig von der Blocklänge beschreibt, die so genannte '''Quellentropie''' (''source entropy''):
+== Siehe auch ==
- <math>h = \lim_{n \to \infty}H^{(n)} = \lim_{n \to \infty} h_n</math>
+* [[Entropie (Informationstheorie)]]
+* [[Entropieschätzung]]
+* [[Symbolische Dynamik]]
+== Literatur ==
-Es gelten die [[Ungleichung]]en
+* Martin Werner: ''Information und Codierung.'' Grundlagen und Anwendungen, 2. Auflage, Vieweg + Teubner Verlag, Wiesbaden 2008, ISBN 978-3-8348-0232-3.
+* Peter Bocker: ''Datenübertragung''. Band I – ''Grundlagen''. Springer Verlag, Berlin / Heidelberg 1976, ISBN 978-3-662-06499-3.
- <math>h \le H^{(n)} \le H(x_n) \le \log |X|</math>
+== Weblinks ==
+* [http://www.hawo.stw.uni-erlangen.de/~siflfran/uni/IuK/Formelsammlungen/infth.pdf Informationstheorie] (abgerufen am 8. März 2018)
+* [https://www2.ostfalia.de/export/sites/default/de/pws/lajmi/Lehre/Codierungstheorie/pdf/Codierung_2008_-_2009_2.pdf Kodierungs- und Informationstheorie] (abgerufen am 8. März 2018)
+* [https://graphics.ethz.ch/teaching/former/infotheory0607/Downloads/slides3_1.pdf Entropie] (abgerufen am 8. März 2018)
+* [https://graphics.ethz.ch/teaching/infotheory_common/skript.pdf Information und Kommunikation] (abgerufen am 8. März 2018)
+== Einzelnachweise ==
-''Siehe auch:'' [[Kullback-Leibler Entropie]], [[Zeitreihenanalyse]]
+<references>
+<ref name="cover">T. H. Cover, J. A. Thomas, ''Elements of Information Theory'', S. 16 f, 2nd Edition, 2006, Wiley Interscience, ISBN 978-0-471-24195-9</ref>
+</references>
+[[Kategorie:Informationstheorie]]
-==Weblinks==
-* http://www.data-compression.com/theory.html#entropy
-* http://et.ti.uni-mannheim.de/lehre/skripten/et/et16.pdf
-* http://summa.physik.hu-berlin.de/~frank/download/web-tueb.pdf