Verbundentropie

Die Blockentropie oder Verbundentropie ist die Verallgemeinerung der Shannonentropie für eine multivariate Zufallsvariable.

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_j aus z (genannt Block), dann gibt die Verbundwahrscheinlichkeit

p_{k}(\mathbf {x} )=p(x_{1}\,x_{2}..x_{k})=p(x_{1})\cdot p(x_{2}..x_{k}|x_{1})

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]_k. Man kann darüber die Blockentropie definieren:

 $H_{k}(\mathbf {x} )=-\sum _{\mathbf {x} \in [X]_{k}}p_{k}(\mathbf {x} )\log p_{k}(\mathbf {x} )$

Die Menge [X]_k wird in den meisten Fällen auch Realisierungen enthalten, die nicht in I vorkommen, also p_k(x)=0. Die Anzahl aller möglichen Realisierungen |[X]_k| ist gemäß Kombinatorik gegeben durch:

|[X]_{k}|=|Z|^{k}

Bedingte Entropie

Die Unsicherheit eines Symbols x_j eines k-Blocks ist:

 $H^{(k)}=H(x_{k}|x_{k-1},...,x_{1})={\frac {H_{k}}{k}}$

Ebenso aus der Blockentropie abgeleitet ist die Entropie pro Zeitschritt oder bedingte Entropie bzw. Entropierate. Sie gibt an, wie groß die Unsicherheit ist, ein bestimmtes Symbol nach einer Kette von k vorhergehenden Symbolen erwarten zu können - anders ausgedrückt, mit welcher Sicherheit x_k+1 vorherzusagen ist

 $h_{k}=H_{k+1}-H_{k}$

mit

 $h_{0}=H_{1}$

Der zweidimensionale Fall

Wenn das Auftreten eines Zeichens x_i nur vom vorherigen Zeichen x_j abhängt (wie etwa in der "101010..."-kette) erhält man aus

Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle H(X,Y) = \sum_i \sum_j p(x_i,y_j) \log p(x_i,y_j) }

und

p(x_{i},y_{j})=p(x_{i})p(y_{j}|x_{i})

den Ausdruck

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

wobei x_i den Zustand, d.h. die Folge der vorhergehenden Symbole, bezeichnet und p(y_j|x_i) ist die bedingte Wahrscheinlichkeit von y_j gegeben x_i. Die Verbundwahrscheinlichkeit von x_i und y_j, p(x_i,y_j) ist wiederum die Wahrscheinlichkeit des gemeinsamen Auftretens von x_i und y_j.

Es lautet also hier h₁:

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})

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):

 $h=\lim _{n\to \infty }H^{(n)}=\lim _{n\to \infty }h_{n}$

Es gelten die Ungleichungen

 $h\leq H^{(n)}\leq H(x_{n})\leq \log |X|$

Siehe auch: Kullback-Leibler Entropie, Zeitreihenanalyse

Weblinks