++ Mathe Formeln ++ Mathematik Lexikon ++ Lösungen ++ Hausaufgaben ++ Algebra ++ Lernen ++ Übungen ++ Schule ++ Geometrie ++

Navigation

Mathematik Begriffe
A B C D E
F G H I J
K L M N O
P Q R S T
U V W X Y
Z 123      
Goldkurs

Mathematik Begriff Erklärung Blockentropie Formel Hilfe Hausaufgabeb
Blockentropie

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 xj 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 pk(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(X1,X2) für zwei Zufallsvariablen X1 und X2 ist gegeben durch

H(X1,X2) = H(X1) + H(X2 | X1)

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

H(X1,X2) = H(X1) + H(X2)

Die bedingte Entropie wird im Folgenden erläutert.

Inhaltsverzeichnis
1 Bedingte Entropie

1.1 Der zweidimensionale Fall

2 Quellentropie
3 Siehe auch
4 Weblinks

 

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 (x1,..,xk), lässt sich die bedingte Entropie hk definieren als die Unsicherheit eines Symbols xk+1 (nach einem bestimmten vorgegebenen k-Block):

hk: = Hk + 1 - Hk , mit h0: = H1

wobei Hk+1 bzw. Hk die Blockentropie ist.

 

Der zweidimensionale Fall

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

H(X,Y) = ? ? p(xi,yj)logp(xi,yj)
i j

und

p(xi,yj) = p(xi)p(yj | xi)

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 xi den Zustand, d.h. die Folge der vorhergehenden Symbole, bezeichnet und p(yj|xi) ist die bedingte Wahrscheinlichkeit von yj gegeben xi. Die Verbundwahrscheinlichkeit von xi und yj, p(xi,yj) ist wiederum die Wahrscheinlichkeit des gemeinsamen Auftretens von xi und yj.

Es folgt für die bedingte Entropie h1, also die Unsicherheit eines Symbols nach einem 1-Block:

h1 = H2 - H1 = H(X) + H(Y | X) - H(X) = H(Y | X) = - ? p(xi) ? p(yj | xi)log2p(yj | xi)
i j

 

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 \le H^{(n)} \le H(x_n) \le \log |X|

 

 

Siehe auch

Kullback-Leibler Entropie, Zeitreihenanalyse

 

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
Dieser Artikel ( Blockentropie ) stammt aus Wikipedia, der freien Enzyklopädie
und steht unter der GNU Free Documentation Licence. 
+++ Mathe Formeln ++ Mathematik Lexikon ++ Lösungen ++ IMPRESSUM ++ Algebra ++ Lernen ++ Übungen ++ Schule ++ Geometrie +++