Verbundentropie

Die Verbundentropie bzw. Blockentropie 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}

Eine allgemeinere Formulierung der Verbundentropie H(X₁,X₂) für zwei Zufallsvariablen X₁ und X₂ ist gegeben durch

H(X_{1},X_{2})=H(X_{1})+H(X_{2}|X_{1})

die Summe aus der Entropie von X₁ und der bedingten Entropie von X₂ unter gegebenem X₁. Sind X₁ und X₂ unabhängig, dann gilt (äquivalent zur bedingten Wahrscheinlichkeit):

H(X_{1},X_{2})=H(X_{1})+H(X_{2})

Die bedingte Entropie wird im Folgenden erläutert.

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.

Formal ist die bedingte Entropie H(X|Y) definiert durch:

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

Für den Fall, dass X und Y unabhängig sind, ergibt sich:

H(Y|X)=H(Y)

Übertragen auf eine multivariate Zufallsvariable X der Länge k (siehe oben), als Darstellung für einen k-Block von Symbolen (x₁,..,x_k), lässt sich die bedingte Entropie h_k definieren als die Unsicherheit eines Symbols x_k+1 (nach einem bestimmten vorgegebenen k-Block):

h_{k}:=H_{k+1}-H_{k}{\mbox{ , mit }}h_{0}:=H_{1}

wobei H_k+1 bzw. H_k die Blockentropie ist.

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

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

Verbundentropie

Inhaltsverzeichnis

Bedingte Entropie

Der zweidimensionale Fall

Quellentropie

Weblinks