Entropie: IT: Unterschied zwischen den Versionen
Rho (Diskussion | Beiträge) |
|||
Zeile 269: | Zeile 269: | ||
t 11 |
t 11 |
||
Gibt es dazu einen Standard ? |
Gibt es dazu einen Standard ? |
||
Siehe dazu http://rosalind.info/problems/ini/ |
|||
1 gagcagcgcg cgcaagcagg ccaggggaag gtgggcgcag gtgaggggcc gaggtgtgcg |
1 gagcagcgcg cgcaagcagg ccaggggaag gtgggcgcag gtgaggggcc gaggtgtgcg |
Version vom 3. November 2014, 17:22 Uhr
Zurück zur Übersicht
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/38/Randomwalk0.png/300px-Randomwalk0.png)
Entropie in der Informationstheorie und Mathematik
Entropie ist ein Maß für die Menge an Zufallsinformation, die in einem System oder einer Informationsfolge steckt.
Man muss bei jedem Zufallsereignis mit mehreren möglichen Folgen drei Begriffe auseinanderhalten:
- die Wahrscheinlichkeit jeder Möglichkeit
- die Zahl der Möglichkeiten (Ereignisraum eines Zufallsexperimentes)
- die Menge an Zufallsinformation = Entropie in der Mathematik
Dabei ist die Entropie eher verwandt mit dem Begriff Zahl der Möglichkeiten, denn Sie wird aus der Zahl der Möglichkeiten abgeleitet und nur durch das Logarithmieren kleiner und handhabbarer gemacht.
Für den idealen einmaligen Münzwurf gilt dann beispielsweise:
- Wahrscheinlichkeit jeder Möglichkeit 0,5
- Zahl der Möglichkeiten: 2
- Entropie = Log2(2) = 1 bit
Wiederholt man den Münzwurf 2 mal, dann gilt:
- Wahrscheinlichkeit jeder Möglichkeit 0,25
- Zahl der Möglichkeiten: 4
- Entropie = Log2(4) = 2 bit
Der Begriff in der Informationstheorie ist in Analogie zur Entropie in der Thermodynamik und Statistischen Mechanik benannt. Beide Begriffe haben Gemeinsamkeiten, sind aber nicht ohne weiteres gleich zu setzen.
Das informationstheoretische Verständnis des Begriffes Entropie geht auf Claude Elwood Shannon zurück und existiert seit etwa 1948. In diesem Jahr veröffentlichte Shannon seine fundamentale Arbeit A Mathematical Theory of Communication und begründete damit die moderne Informationstheorie.
Definition
Shannon definierte die Entropie H einer gegebenen Information I über einem Alphabet Z durch
- ,
wobei pj die Wahrscheinlichkeit ist, mit der das j-te Symbol zj des Alphabets Z im Informationstext I auftritt.
Lassen Sie sich durch diese Formel nicht so schnell verwirren. Sie kommen am besten klar mit der Formel, wenn Sie ein paar Rechenaufgaben zu dieser Formel lösen. Siehe Entropie#Rechenaufgaben
Eine andere Methode, um diese Formel zu verstehen, bietet jeder Computer mit einer Programmierumgebung. Man schreibt ein kleines Computerprogramm und läßt die Variablen in einer Schleife variieren. Schon wird einem die Sache klarer, nach dem Motto: Habe ich es nicht programmiert, dann habe ich es noch nicht verstanden.
Im Folgenden wird die Formel in ihre Einzelteile zerlegt, um sie verständlich zu machen.
Summenzeichen
Das Zeichen Σ, das Sie vielleicht noch nicht kennen, steht dabei nur für eine Summe mit mehreren Teilen.
Beispiel:
Beispiel 2:
Oder allgemein:
Siehe auch http://de.wikipedia.org/wiki/Summe#Notation_mit_dem_Summenzeichen
log2
Wenn Sie das Zeichen Logarithmus nicht verstehen , schauen Sie sich einfach einmal folgende Seite an:
Bei der Shannonschen Definition wird der binäre Logarithmus verwendet. Dieser findet sich leider nicht auf den üblichen kleinen Rechnern im PC.
Deswegen können Sie als Linuxuser bc nutzen: Linux-Praxisbuch:_bc Oder folgende Programme verwenden:
- http://de.wikibooks.org/wiki/Gambas:_Rechnen#Logarithmus
- Gambas Logarithmus Programm
- http://www.madeasy.de/2/prglog.htm
- VB Logarithmus Programm
Auf normalen Taschenrechnern kann man auch den binären Logarithmus mit dem exp (ln) logarithmus berechnen: log(2)x := ln(x) / ln(2)
Wahrscheinlichkeit p
In die Formel geht die Wahrscheinlichkeit p ein. Wenn Sie sich noch nicht mit Wahrscheinlichkeitswerten beschäftigt haben, dann schauen Sie einfach einmal folgende Seite an:
p kann Werte zwischen 0 und 1 annehmen.
- p = 0
- Unmögliches Ereignis
- p = 1
- Sicheres Ereignis
- p = 0,5
- Wahrscheinlichkeit mit einer idealen Münze Zahl oder Wappen zu werfen.
Zahl der Möglichkeiten (Ereignisraum eines Zufallsexperimentes)
Die Bedeutung des Begriffes Entropie erschließt sich am besten, wenn man sich klar macht, wieviele Möglichkeiten in einer Zufallsauswahl gegeben sind. Dann muss man noch unterscheiden, ob alle Möglichkeiten gleichberechtigt sind oder ob die Wahrscheinlichkeit der einzelnen Möglichkeiten unterschiedlich ist.
Beispiel: Zahl der Möglichkeiten bei einem Wurf
Münze: Zahl der Möglichkeiten 2 gleichberechtigt Reißnagel: Zahl der Möglichkeiten 2 verschieden wahrscheinlich 6er Würfel: Zahl der Möglichkeiten 6 gleichberechtigt
Einheit bit
Eigentlich ist die berechnete Entropie dimensionslos. Trotzdem erhält sie eine Einheit, nämlich das bit. Die Einheit Shannon ist unüblich und hat sich nicht durchgesetzt.
H multipliziert mit der Anzahl der Zeichen im Informationstext ergibt die mindestens notwendige Anzahl von Bits, die zur Darstellung der Information notwendig sind.
Prinzipiell lässt sich die Berechnung der Entropie auch auf andere Zahlensysteme (etwa Oktalsystem, Hexadezimalsystem) als das Binärsystem (Basis 2) übertragen. In diesem Fall wird der Logarithmus nicht zur Basis 2, sondern zur entsprechenden informationstheoretischen Basis des Zahlensystems gebildet.
Die Verallgemeinerung der Entropie für eine multivariante Zufallsvariable wird Blockentropie beziehungsweise Verbundentropie genannt.
Interpretation
Entropie ist grob gesagt ein Maß für die Menge an Zufallsinformation, die in einem System oder einer Informationsfolge steckt. Dabei ist die Einheit der Zufallsinformation 1 bit definiert als die Informationsmenge, die in einer Zufallsentscheidung eines idealen Münzwurfes enthalten ist. Ein idealer Münzwurf hat nur zwei Möglichkeiten – Wappen oder Zahl –, die beide mit der gleichen Wahrscheinlichkeit p = 0,5 auftreten.
Shannons ursprüngliche Absicht, die Entropie als das Maß der benötigten Bandbreite eines Übertragungskanals zu nutzen, wurde schnell verallgemeinert. Die Entropie wurde generell als ein Maß für den Informationsgehalt betrachtet. Wenn die Entropie bei einer Binärentscheidung beispielsweise einen Wert von 1 hat, dann gilt die Information als zufällig. Bei einer kleinen Entropie enthält der Informationstext Redundanzen oder statistische Regelmäßigkeiten. Die Zahl gibt intuitiv die durchschnittliche Information an, die in einem Symbol der Quelle enthalten ist.
Die rein statistische Berechnung der informationstheoretischen Entropie nach obiger Formel ist gleichzeitig ihre Beschränkung. Beispielsweise ist die Wahrscheinlichkeit, eine 0 oder 1 in einer geordneten Zeichenkette "1010101010..." zu finden, genauso groß, wie in einer Zeichenkette, die durch statistisch unabhängige Ereignisse (etwa wiederholten Münzwurf) entstanden ist. Daher ist Shannons Entropie für beide Zeichenketten identisch, obwohl man intuitiv die erste Kette als weniger zufällig bezeichnen muss. Eine angemessenere Definition der Entropie einer Zeichenkette liefert die bedingte Entropie und Quellentropie, die beide auf Verbundwahrscheinlichkeiten aufbauen.
In engem Zusammenhang zur bedingten Entropie steht auch die Transinformation, die die Stärke des statistischen Zusammenhangs zweier Zufallsgrößen angibt.
Beispiel: Münzwurf
Bei einem Münzwurf sind idealerweise „Kopf“ oder „Zahl“ gleichwahrscheinlich. Wenn man die Entropie als Maß für die Ungewissheit auffasst, wird sie in diesem einfachen dualen System einen maximalen Wert aufweisen. Es ist völlig ungewiss, ob beim nächsten Wurf „Kopf“ oder aber „Zahl“ geworfen wird. Die Entropie wird hier als 1 bit definiert.
Anders bei einer gezinkten Münze, etwa einer Münze, die im Mittel in 60 % der Fälle „Kopf“ und nur in 40 % der Fälle „Zahl“ anzeigt. Die Ungewissheit ist hier geringer als bei der normalen Münze, da man eine gewisse Präferenz für „Kopf“ hat. Gemessen als Entropie liegt die Ungewissheit bei nur noch etwa 0,971.
Bei der Münze ergänzen sich die Wahrscheinlichkeiten beider Möglichkeiten zur Summe 1, da es nur zwei Möglichkeiten gibt.
Die Entropie lässt sich in diesem Fall mit Shannons Formel berechnen:
Wenn sie den Begriff log2 nicht verstehen ( binärer Logarithmus) , dann schauen sie sich einmal folgende Seiten durch:
- http://www.madeasy.de/2/log.htm
- http://de.wikibooks.org/wiki/Mathematik:_Schulmathematik:_Logarithmieren
Ersetzt man durch den Ausdruck , so erhält man die Formel
Ist p = 0,5 , dann kann man H errechnen:
- H = - ( 0,5 * (-1) + 0,5 *(-1))
- H = - ( - 0,5 - 0,5 )
- H = 1
Wenn p verschiedene Werte zwischen 0 und 1 annehmen kann , kann man den Zusammenhang zwischen p und H grafisch folgendermaßen darstellen:
![](http://upload.wikimedia.org/wikibooks/de/thumb/5/56/Entropq.gif/300px-Entropq.gif)
Für jedes kann man daraus die Entropie direkt ablesen. Die Funktion ist symmetrisch zur Geraden . Sie fällt bei sehr steil zu einem Entropie-Wert von 0 ab. Auch bei Werten, die sich dem sicheren Ereignis von nähern, fällt die Entropie auf 0 ab.
Dieser Zusammenhang gilt jeweils für ein Zufallsereignis. Bei mehreren Zufallsereignissen muss man die einzelnen Entropien zusammenzählen und man kann so leicht Entropiewerte über 1 erreichen. Die Wahrscheinlichkeit dagegen bleibt auch bei Wiederholungen definitionsgemäß immer zwischen 0 und 1!
Wiederholt man den Münzwurf zweimal, wächst die Zahl der Möglichkeiten auf vier. Die Wahrscheinlichkeit jeder einzelnen Möglichkeit liegt bei 0,25. Die Entropie des zweimaligen Münzwurfes ist dann 2 bit. Wenn man einen idealen Münzwurf mehrfach wiederholt, dann addiert sich die Entropie einfach. Die Entropie einer Reihe von 20 idealen Münzwürfen berechnet sich einfach: . Dies wird im folgenden Bild dargestellt.
![](http://upload.wikimedia.org/wikibooks/de/thumb/4/48/Entrosum.gif/300px-Entrosum.gif)
Man kann nicht einfach aus einem Wert der Wahrscheinlichkeit die Entropie ausrechnen. Die Entropie betrifft den gesamten Zufallsprozess. Jede Teilwahrscheinlichkeit eines möglichen Ergebnisses geht in die Berechnung der Entropie des Gesamtprozesses ein. Die Angabe einer Teilentropie für jedes mögliche Ergebnis macht dabei wenig Sinn. In der Shannonschen Entropieformel sollte also die Summe der Wahrscheinlichkeiten 1 ergeben, sonst kann es ein missverständliches Ergebnis geben.
Speichert man eine Folge von Münzwürfen als Bitfolge, dann bietet es sich an, „Kopf“ stets durch 0 und „Zahl“ stets durch 1 zu repräsentieren (oder umgekehrt). Bei der gezinkten Münze sind kompaktere Kodierungen möglich. Diese erhält man beispielsweise durch den Huffman-Kode.
Beispiel: Idealer Würfel
Bei einem Wurf eines idealen Würfels mit sechs Möglichkeiten ist die Entropie größer als 1. Allgemein ist sie größer als 1 für ein Zufallsereignis aus einem Zufallsexperiment mit mehr als zwei gleichberechtigten Möglichkeiten im Ergebnisraum. Ihr Wert wird bei gleichwahrscheinlichen Möglichkeiten im Ergebnisraum folgendermaßen berechnet:
- .
Beim idealen Würfel sind sechs Möglichkeiten im Ergebnisraum. Daraus folgt die Entropie für Einmal Werfen:
![](http://upload.wikimedia.org/wikibooks/de/thumb/0/05/Entrurne.gif/400px-Entrurne.gif)
Einfach zu berechnen ist die Entropie eines Wurfes eines idealen Achterwürfels: Er hat acht gleichberechtigte Möglichkeiten.
Die Entropie eines Wurfes mit dem idealen Achterwürfel entspricht der Entropie von drei Würfen mit der idealen Münze.
Die nebenstehende Abbildung stellt den Zusammenhang zwischen der Entropie und der Zahl der gleichberechtigten Möglichkeiten eines Zufallsexperimentes dar.
Rechenaufgaben
Reißnagel
![](http://upload.wikimedia.org/wikibooks/de/a/ac/Reisnagl.png)
1. Berechnen Sie die Entropie des Wurfes eines Reißnagels, dessen Wahrscheinlichkeit auf dem Rücken zu liegen p = 0,3 beträgt und dessen Wahrscheinlichkeit nicht auf dem Rücken zu liegen 0,7 beträgt. Benutzen Sie dazu die Formel von Shannon.
Der Reissnagel ist das Beispiel eines binären Zufallsgenerators mit ungleicher Zufallsverteilung p ungleich q.
- Lösung: H = 0,88
- Lösungsweg: Siehe Entropie:_Loesungen
8er Würfel
2. Berechnen Sie die Entropie des Wurfes eines idealen achter Würfels, dessen Wahrscheinlichkeit für jede Seite p = 1/8 ist.
- Lösung: H = 3
- Lösungsweg: Siehe Entropie:_Loesungen
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/36/Two_red_dice_01.svg/300px-Two_red_dice_01.svg.png)
6er Würfel
3. Berechnen Sie die Entropie des Wurfes zweier idealer sechser Würfel, die gleichzeitig geworfen werden.
- Lösung: H = 4,34 für nicht unterscheidbare Würfel
- Lösung: H = 5,169925001442 für unterscheidbare Würfel
- Lösungsweg: Entropie:_Loesungen#Aufgabe_3
Summe 2 * Würfel
4. Berechnen Sie die Summe der Entropien zweier Würfe eines idealen sechser Würfels, der 2 mal hintereinander geworfen wird.
- Lösung: H = 5,169925001442
- Lösungsweg: Entropie:_Loesungen#Aufgabe_4
Urne mit 3 Kugeln
5. Sie haben eine Urne mit einer roten , einer weißen und einer schwarzen Kugel. Die Kugeln sind beim Ziehen nicht zu unterscheiden.
- a) Berechnen Sie die Wahrscheinlichkeit des Ziehens für jede Farbe.
- b) Berechnen Sie die Entropie für einen Zug aus der Urne.
- c) Berechnen Sie die Entropie für 2 Züge aus der Urne.
- Lösung a: p = 1 /3
- Lösung b: H = 1,584962500721
- Lösung c: H = 3,169925001442 mit Zurücklegen
- Lösung c: H = 2,584962500721 ohne Zurücklegen
- Lösungsweg: Entropie:_Loesungen#Aufgabe_3
![](http://upload.wikimedia.org/wikibooks/de/7/7d/Urne.png)
6er Urne
6. Wieviel Bit an Entropie steckt in jedem Zug dieser 6er Urne unter der Voraussetzung, daß alle Kugeln gleichwahrscheinlich p = 1/6 gezogen werden ?
- Antwort: H = 2,585... bit
- Lösungsweg: Siehe Entropie:_Loesungen
6er Urne
7. Wie groß ist die Summe der Entropien der 6er Urne unter der Voraussetzung, daß alle Kugeln gleichwahrscheinlich p = 1/6 gezogen werden und das die Kugeln nach jedem Zug nicht mehr zurückgelegt werden? Sie ziehen bis die Urne leer ist. Berechnen Sie erst die Wahrscheinlichkeit für jeden Zug, dann die Entropie für jeden Zug und dann die Summe der Entropien.
- Lösung:H = 9,491853096329
- Lösungsweg: Siehe Entropie:_Loesungen
Lottoziehung
8. Wie groß ist die Entropie einer fiktiven Lottoziehung 1 aus 1 Million Möglichkeiten.
- Lösung:H = 19,931568569324
- Lösungsweg: Siehe Entropie:_Loesungen
Kartenspiel
9. Sie haben ein normales Kartenspiel mit 4 Farben und 13 Karten je Farbe (As, 2, 3, 4, 5, 6, 7, 8, 9, 10, Bube, Dame, König). Die Karten werden ausführlich gemischt. Wie groß ist die Entropie beim Zug einer Karte ? Beachten Sie dazu die Zahl der gleichberechtigten Möglichkeiten und berechnen Sie dann die Entropie.
- Lösung:H = 5,70043971814109
- Lösungsweg: Siehe Entropie:_Loesungen
9a. Sie haben ein Kartenspiel mit 4 Farben und 9 Karten je Farbe. Gesamtzahl der Karten 36.Die Karten werden ausführlich gemischt. Wie groß ist die Entropie beim Zug einer Karte ? Beachten Sie dazu die Zahl der gleichberechtigten Möglichkeiten und berechnen Sie dann die Entropie.
- Lösung: H = 5,17
- Lösungsweg: Siehe Entropie:_Loesungen
Entropie und Gene
Sie haben eine Gensequenz und versuchen die Entropie dieser Sequenz zu berechnen ? Macht so eine Berechnung überhaupt Sinn ? Wie ändert sich die Berechnung, wenn man immer Triplets betrachtet ? Es sind ja immer zwei Basenpaare gekoppelt g und c sowie a und t, kann man das Ausnutzen, um die Redundanz zu reduzieren ? Wie schaut eine 01 Kodierung für Gene aus ? Beispielsweise
a 00 c 01 g 10 t 11
Gibt es dazu einen Standard ?
Siehe dazu http://rosalind.info/problems/ini/
1 gagcagcgcg cgcaagcagg ccaggggaag gtgggcgcag gtgaggggcc gaggtgtgcg 61 caggacttta gccggttgag aaggatcaag caggcatttg gagcacaggt gtctagaaac 121 ttttaagggg ccggttcaag aaggaaaagt tcccttctgc tgtgaaacta tttggcaaga 181 ggctggaggg cccaatggct gcaaaattgc aacccaacat tcccaaagcc aagagtctag 241 atggcgtcac caatgacaga accgcatctc aagggcagtg gggccgtgcc tgggaggtgg 301 actggttttc actggcgagc gtcatcttcc tactgctgtt cgcccccttc atcgtctact 361 acttcatcat ggcttgtgac cagtacagct gcgccctgac cggccctgtg gtggacatcg 421 tcaccggaca tgctcggctc tcggacatct gggccaagac tccacctata acgaggaaag 481 ccgcccagct ctataccttg tgggtcacct tccaggtgct tctgtacacg tctctccctg 541 acttctgcca taagtttcta cccggctacg taggaggcat ccaggagggg gccgtgactc 601 ctgcaggggt tgtgaacaag tatcagatca acggcctgca agcctggctc ctcacgcacc 661 tgctctggtt tgcaaacgct catctcctgt cctggttctc gcccaccatc atcttcgaca 721 actggatccc actgctgtgg tgcgccaaca tccttggcta tgccgtctcc accttcgcca 781 tggtcaaggg ctacttcttc cccaccagcg ccagagactg caaattcaca ggcaatttct 841 tttacaacta catgatgggc atcgagttta accctcggat cgggaagtgg tttgacttca 901 agctgttctt caatgggcgc cccgggatcg tcgcctggac cctcatcaac ctgtccttcg 961 cagcgaagca gcgggagctc cacagccatg tgaccaatgc catggtcctg gtcaacgtcc 1021 tgcaggccat ctacgtgatt gacttcttct ggaacgaaac ctggtacctg aagaccattg 1081 acatctgcca tgaccacttc gggtggtacc tgggctgggg cgactgtgtc tggctgcctt 1141 atctttacac gctgcagggt ctgtacttgg tgtaccaccc cgtgcagctg tccaccccgc 1201 acgccgtggg cgtcctgctg ctgggcctgg tgggctacta catcttccgg gtggccaacc 1261 accagaagga cctgttccgc cgcacggatg ggcgctgcct catctggggc aggaagccca 1321 aggtcatcga gtgctcctac acatccgccg acgggcagag gcaccacagc aagctgctgg 1381 tgtcgggctt ctggggcgtg gcccgccact tcaactacgt cggcgacctg atgggcagcc 1441 tggcctactg cctggcctgt ggcggtggcc acctgctgcc ctacttctac atcatctaca 1501 tggccatcct gctgacccac cgctgcctcc gggacgagca ccgctgcgcc agcaagtacg 1561 gccgggactg ggagcgctac accgccgcag tgccttaccg cctgctgcct ggaatcttct 1621 aagggcacgc cctagggaga agccctgtgg ggctgtcaag agcgtgttct gccaggtcca 1681 tgggggctgg catcccagct ccaactcgag gagcctcagt ttcctcatct gtaaactgga 1741 gagagcccag cacttggcag gtgtccagta cctaatcacg ctctgttcct tgcttttgcc 1801 ttcaagggaa ttccgagtgt ccagcactgc cgtattgcca gcacagacgg attttctcta 1861 atcagtgtcc ctgggcagga ggatgaccca gtcaccttta ctagtccttt ggagacaatt 1921 tacctgtatt aggagcccag gccacgctac actctgccca cactggtgag caggaggtct 1981 tcccacgccc tgtcattagg ctgcatttac tcttgctaaa taaaagtggg agtggggcgt 2041 gcgcgttatc catgtattgc ctttcagctc tagatccccc tcccctgcct gctctgcagt 2101 cgtgggtggg gcccgtgcgc cgtttctcct tggtagcgtg cacggtgttg aactgggaca 2161 ctggggagaa aggggctttc atgtcgtttc cttcctgctc ctgctgcaca gctgccagga 2221 gtgctctgcc tggagtctgc agacctcaga gaggtcccag cactggctgt ggctttcagg 2281 tgtaggcagg tgggctctgc ttcccgattc cctgtgagcg cccaccctct cgaaagaatt 2341 ttctgtcttg ccctgtgact gtgcagactc tggctcgagc aacccgggga acttcaccct 2401 caggggcctc tccacacctt ctccagcgag gaggtctcag tcccagcctc gggagggcac 2461 ctccttttct gtgctttctt ccctgaggca ttcttcctca tccctagggt gttgtgtaga 2521 actcttttta aactctatgc tccgagtaga gttcatcttt atattaaact tcccctgttc 2581 aaaaaaaaaa aaaaaaa
Links zu weiteren Übungsaufgaben
- http://www.tf.uni-kiel.de/matwis/amat/mw1_ge/kap_5/exercise/e5_3_1.html
- einfache Übungsaufgaben in Kombinatorik
Die Entropie beliebiger binärer Folgen
Will man die Entropie verstehen kann man sich mit den einfachsten Informationsfolgen beschäftigen in denen der Unterschied zwischen hoher und niedriger Entropie schon auf den ersten Blick erkennbar ist. Man nimmt dazu binäre Zahlenfolgen von Null und Eins und versucht eine Aussage zur Entropie zu treffen.
Chaitin hat dazu ein einfaches Beispiel angegeben:
Was ist der Unterschied zwischen
10101010101010101010
und
01101100110111100010
wenn man die Folgen vom Standpunkt Entropie und Ordnung her betrachtet.
Siehe auch
- http://www.cs.auckland.ac.nz/CDMTCS/chaitin/index.html bzw *http://www.cs.auckland.ac.nz/CDMTCS/chaitin/sciamer.html und
- chaitin G.J. 1975 scientific American 232 S 47 -52
Die erste Sequenz ist hochgeordnet und kann leicht komprimiert werden: zehnmal "10" Die zweite Sequenz ist eine Zufallsfolge, die durch 20 maliges Werfen einer Münze gewonnen wurde. Das ist der Unterschied. Deswegen ist auch die Entropie in der ersten Folge niedrig und nahe Null. Die Entropie der zweiten Folge ist hoch.
Wie kann man nun die Entropie dieser beiden 01 Sequenzen berechnen.
Dazu bedient man sich eines statistischen Testes auf Zufälligkeit, des sogenannten Runtests
Programmierung des Runtestes
Hier findet sich ein Programm für den Runtest.
Leider funktioniert der Runtest nicht bei beliebigen 01 Sequenzen , sondern nur wenn die Zahl von 0 und 1 ungefähr gleich ist. Beispielsweise kann man eine Sequenz 00000000000000000010 im Runtest nicht auf ihre Zufälligkeit überprüfen.
Beispiellisting einer Entropieberechnung mit dem Runtestes für eine 01 Folge fester Länge
Programmiersprache Gambas
- Die Länge der 01 Folge ist variierbar , hier s = 8. ( Länge ist die Variable s im Listing)
- Die Zahl der Nullen und Einsen ist zur Vereinfachung gleich groß.
- Das Programm startet von alleine.
- Die Ergebnisausgabe erfolgt im Direkfenster.
- Bewertung:
- pz Werte um die 0 sind ein Zeichen hoher Entropie. Pz-Werte über 1,5 oder unter -1,5 sind ein Zeichen niedriger Entropie
PUBLIC SUB Form_Open() s AS Integer 'Laenge der Binaerzahl z AS Integer 'Zaehler von 0 bis 2^s-1 zz AS Integer 'Zaehler von 1 bis alle Varianten mit ozaehler = izaehler t AS String 'binaerzahl ozaehler AS Integer 'Zahl der Nullen izaehler AS Integer 'Zahl der Einser tt AS String 'binaerzahl als String n AS Integer 'Laenge der Binaerzahl char AS String UM AS Float varianz AS Float svar AS Float 'Quadratwurzel der Varianz zwei AS Integer summe AS Integer run AS Integer nn AS Integer chari AS String charnext AS String runzaehler AS Integer pz AS Float 'Pruefvariable entspricht dem Entropiewert der Folge 'pz Werte um die 0 sind ein Zeichen hoher Entropie. 'Pz-Werte über 1,5 oder unter -1,5 sind ein Zeichen niedriger Entropie s = 10 'Laenge der 01 Folge zz = 0 FOR z = 0 TO (2^s - 1) t = Bin$(z,s) tt = Str(t) 'PRINT "tt = " & tt ozaehler = 0 izaehler = 0 FOR n = 1 TO Len(tt) char = Mid$(tt, n, 1) SELECT CASE TRUE CASE char = "0" ozaehler = ozaehler + 1 CASE char = "1" izaehler = izaehler + 1 END SELECT NEXT 'PRINT izaehler 'PRINT ozaehler IF izaehler = ozaehler THEN zz = zz + 1 t = tt PRINT "zz = " & zz & " t = " & t; 'runtest UM = 2 * s/2 * s/2 /( s/2 + s/2 ) + 1 'PRINT "UM = " & UM zwei = 2 * s/2 * s/2 summe = s varianz = zwei *( zwei - summe) / (summe * summe * (summe - 1)) IF varianz < 0 THEN varianz = -varianz 'PRINT "Varianz = " & varianz runzaehler = 1 FOR nn = 1 TO Len(t) - 1 chari = Mid$(t, nn, 1) charnext = Mid$(t, nn + 1, 1) IF chari <> charnext THEN runzaehler = runzaehler + 1 NEXT 'PRINT " runzaehler = " & runzaehler; svar = Sqr(varianz) pz = ( runzaehler - UM)/svar PRINT " pz = " & Str(pz) 'PRINT Str(pz) ENDIF NEXT END
Ergebnisausgabe:
zz = 1 t = 00001111 pz = -2,291287847478 zz = 2 t = 00010111 pz = -0,763762615826 zz = 3 t = 00011011 pz = -0,763762615826 zz = 4 t = 00011101 pz = -0,763762615826 zz = 5 t = 00011110 pz = -1,527525231652 zz = 6 t = 00100111 pz = -0,763762615826 zz = 7 t = 00101011 pz = 0,763762615826 zz = 8 t = 00101101 pz = 0,763762615826 zz = 9 t = 00101110 pz = 0 zz = 10 t = 00110011 pz = -0,763762615826 zz = 11 t = 00110101 pz = 0,763762615826 zz = 12 t = 00110110 pz = 0 zz = 13 t = 00111001 pz = -0,763762615826 zz = 14 t = 00111010 pz = 0 zz = 15 t = 00111100 pz = -1,527525231652 zz = 16 t = 01000111 pz = -0,763762615826 zz = 17 t = 01001011 pz = 0,763762615826 zz = 18 t = 01001101 pz = 0,763762615826 zz = 19 t = 01001110 pz = 0 zz = 20 t = 01010011 pz = 0,763762615826 zz = 21 t = 01010101 pz = 2,291287847478 zz = 22 t = 01010110 pz = 1,527525231652 zz = 23 t = 01011001 pz = 0,763762615826 zz = 24 t = 01011010 pz = 1,527525231652 zz = 25 t = 01011100 pz = 0 zz = 26 t = 01100011 pz = -0,763762615826 zz = 27 t = 01100101 pz = 0,763762615826 zz = 28 t = 01100110 pz = 0 zz = 29 t = 01101001 pz = 0,763762615826 zz = 30 t = 01101010 pz = 1,527525231652 zz = 31 t = 01101100 pz = 0 zz = 32 t = 01110001 pz = -0,763762615826 zz = 33 t = 01110010 pz = 0 zz = 34 t = 01110100 pz = 0 zz = 35 t = 01111000 pz = -1,527525231652 zz = 36 t = 10000111 pz = -1,527525231652 zz = 37 t = 10001011 pz = 0 zz = 38 t = 10001101 pz = 0 zz = 39 t = 10001110 pz = -0,763762615826 zz = 40 t = 10010011 pz = 0 zz = 41 t = 10010101 pz = 1,527525231652 zz = 42 t = 10010110 pz = 0,763762615826 zz = 43 t = 10011001 pz = 0 zz = 44 t = 10011010 pz = 0,763762615826 zz = 45 t = 10011100 pz = -0,763762615826 zz = 46 t = 10100011 pz = 0 zz = 47 t = 10100101 pz = 1,527525231652 zz = 48 t = 10100110 pz = 0,763762615826 zz = 49 t = 10101001 pz = 1,527525231652 zz = 50 t = 10101010 pz = 2,291287847478 zz = 51 t = 10101100 pz = 0,763762615826 zz = 52 t = 10110001 pz = 0 zz = 53 t = 10110010 pz = 0,763762615826 zz = 54 t = 10110100 pz = 0,763762615826 zz = 55 t = 10111000 pz = -0,763762615826 zz = 56 t = 11000011 pz = -1,527525231652 zz = 57 t = 11000101 pz = 0 zz = 58 t = 11000110 pz = -0,763762615826 zz = 59 t = 11001001 pz = 0 zz = 60 t = 11001010 pz = 0,763762615826 zz = 61 t = 11001100 pz = -0,763762615826 zz = 62 t = 11010001 pz = 0 zz = 63 t = 11010010 pz = 0,763762615826 zz = 64 t = 11010100 pz = 0,763762615826 zz = 65 t = 11011000 pz = -0,763762615826 zz = 66 t = 11100001 pz = -1,527525231652 zz = 67 t = 11100010 pz = -0,763762615826 zz = 68 t = 11100100 pz = -0,763762615826 zz = 69 t = 11101000 pz = -0,763762615826 zz = 70 t = 11110000 pz = -2,291287847478
![](http://upload.wikimedia.org/wikibooks/de/thumb/3/34/Entropiewerte8er01folgen.png/300px-Entropiewerte8er01folgen.png)
Entropie beliebiger 01 Folgen
Will man den Entropiewert einer beliebigen 01 Folge berechnen, bei der sich die Zahl der Nullen und Einsen deutlich unterscheidet, kann man folgenden Trick benutzen: Man ordnet jeder Ziffer der ursprünglichen 01 Folge eine doppelt solange Binärzahl nach folgendem Schema zu: Aus einer 0 wird eine 01 und aus einer 1 wird eine 10. Beispiel:
000000 > 010101010101 010010 > 011001011001 111111 > 101010101010
Die resultierende Binärzahl ist doppelt solang, ist eindeutig der ursprünglichen Zahl zu zuordnen und kann problemlos mit dem Runtest bearbeitet werden. Aus der berechneten pz Zahl kann man dann die Entropie der ursprünglichen Zahl zurückrechnen, wenn man der größten bzw negativen kleinsten Zahl die Entropie 0 zuordnet. Eine pz Zahl von 0 bedeutet eine maximale Entropie die der Länge der ursprünglichen Binärzahl entspricht. Alle pz Zahlen dazwischen werden einfach proportional umgerechnet. Die proportionale Umrechnung ist willkürlich gewählt, kann man aber als erste Näherung sicher zunächst gelten lassen. So kann man dann jeder beliebigen Binärzahl einen Entropiewert zuordnen. Das ganze kann als Ergänzung zu obigem Basic Programm einfach wiederum als Computerprogramm umgesetzt werden. Man gibt dann eine beliebige 01 Folge ein und der PC berechnet die zugehörige Entropie.
Bei dieser Methode geht allerdings auch Information verloren, denn aus 00001111 wird beispielsweise 0101010110101010. Aus der zunächst symmetrischen Ordnung wird eher eine wiederholende Ordnung mit einem umgekehrten Vorzeichen der pz Zahl.
Sehr schnell merkt man auch, daß die Berechnung aus praktischen Gründen auf eine gewiße Länge der Binärzahl begrenzt bleibt, da sonst der PC zu lange rechnet.
Außerdem ist eine gewisse Eichung sinnvoll. Eine hochgeordnete Folge die nur aus Nullen bzw nur aus Einsern besteht erhält per Definition die Entropie Null und die reine Zufallsfolge mit einem pz unterhalb einer Grenze mit einer festzulegenden Irrtumswahrscheinlichkeit p ( beispielsweise p < 0,05 ) erhält die maximal mögliche Entropie, die der Länge der Binärzahl entspricht.
Entropie und Sprache
Wahrscheinlichkeit und Entropie einzelner Buchstaben der englischen Sprache
Nr Buchstabe Wahrscheinlichkeit Entropie 1 a .0575 4.1 2 b .0128 6.3 3 c .0263 5.2 4 d .0285 5.1 5 e .0913 3.5 6 f .0173 5.9 7 g .0133 6.2 8 h .0313 5.0 9 i .0599 4.1 10 j .0006 10.7 11 k .0084 6.9 12 l .0335 4.9 13 m .0235 5.4 14 n .0596 4.1 15 o .0689 3.9 16 p .0192 5.7 17 q .0008 10.3 18 r .0508 4.3 19 s .0567 4.1 20 t .0706 3.8 21 u .0334 4.9 22 v .0069 7.2 23 w .0119 6.4 24 x .0073 7.1 25 y .0164 5.9 26 z .0007 10.4 27 - .1928 2.4
Entropietexte übernommen aus Wikipedia
Maximaler Entropiewert und Normierung
Möchte man ein normiertes Maß für die Entropie einer beliebigen diskreten Verteilung haben, ist es von Vorteil, die maximal mögliche Entropie, die bei Gleichverteilung der erreicht wird, zur Normierung heranzuziehen. Sei die Anzahl der erlaubten Symbole in über dem Alphabet , dann ist die maximale Entropie gegeben durch:
Daraus folgt beispielsweise für eine Binärverteilung (), also benötigt man 1 Bit pro Zeichen und Zeichen für die komplette Information . Dieser Wert wird erreicht, wenn 0en und 1en gleich häufig vorkommen. Normiert man nun die Entropie einer beliebigen Verteilung mit verschiedenen Symbolen mit erhält man:
Die so erhaltene Entropie wird immer maximal gleich 1.
Um die Entropien von Nachrichten unterschiedlicher Länge vergleichen zu können, hat man die Entropierate eingeführt, die die Entropie auf das einzelne Zeichen bezieht.
Entropietests
Um zu testen, wie gut Daten komprimierbar sind, oder um Zufallszahlen zu testen, werden Entropietests verwendet. Als Zufallszahltest wird die Entropie einer bestimmen Anzahl von Zufallszahlen bestimmt und ab einem Mindestwert, beispielsweise 7 Bit je Byte, gilt er als bestanden. Allerdings gibt es viele solcher Tests, da die Entropie nicht eindeutig ist; sie kann beispielsweise bitbasiert oder bytebasiert sein.
Einfaches Beispiel: Eine Quelle, z. B. ein Spielwürfel oder eine Münze, gibt nur 0xaa (dezimal 170) und 0x55 (dezimal 85) aus und beide mit gleicher Wahrscheinlichkeit. Bitweise ist der output zu 50 % 0 oder 1, byteweise ist er zu 50 % 0xaa oder 0xff. Die bitweise Entropie ist (mit log = ln): H = 1/log(2) *(1/2 *log(1/2) +1/2 *log(1/2)) = 1 während die byteweise Entropie mit H = 1/log(8) *(1/2 *log(1/2) +1/2 *log(1/2)) = 1/3 deutlich kleiner ist.
Der Hersteller dieses Zufallszahlengenerators wird natürlich als Entropie des Geräts die bitweise Entropie, also 1 angeben. Analog wird ein Programmierer eines Kompressionsprogramms möglichst diejenige Basis wählen, bei der die Entropie minimal ist (hier Bytes), sich also die Daten am besten komprimieren lassen.
Dieses Beispiel ist wenig realistisch, da nur zwei von 256 möglichen Bytes verwendet werden, aber wenn auch die anderen Bytes mit einer kleinen Wahrscheinlichkeit von z. B. 1/123456789-tel ausgegeben, so ändert dies an der bitweisen Entropie nichts und die byteweise wird kaum größer; sie bleibt unter 1/2. Erst mit Annäherung der Byte-Wahrscheinlichkeiten an 1/256-tel erreicht die byteweise Entropie den Wert 1, aber dann kann es noch Korrelationen der Bytes geben, also z. B. die Folge 0xaaaa viel häufiger sein als die Folge 0x5555. Dies ist der Hauptgrund, weshalb es viele verschiedene Zufallszahlentests gibt.
Diese Mehrdeutigkeit ist nicht möglich beim Entropiebelag, da dort nicht nur über Wahrscheinlichkeiten summiert wird, sondern über ergodische Wahrscheinlichkeiten von Zuständen, Zustandsübergangswahrscheinlichkeiten und bedingte Wahrscheinlichkeiten. Berechnet wird er mit der Theorie der Markov-Kette. Allerdings ist der Rechenaufwand dafür bei realen Zufallszahlengeneratoren sehr hoch.
Datenkompression und Entropie
Die Entropiekodierung ist ein Kompressionsalgorithmus, um Daten verlustfrei zu komprimieren.
In diesem Zusammenhang spielen die Kreuzentropie sowie die Kullback-Leibler-Divergenz als Maße für die durch eine schlechte Kodierung ausgelösten Verschwendungen von Bits eine Rolle.
Beispiel: Entropiekodierung
- Gegeben sei die Zeichenkette ABBCAADA.
- Die Buchstaben-Wahrscheinlichkeit: ; ;
- Maximalentropie ():
Alternative Möglichkeiten der Informationsquantifizierung
Ein anderer Zugang, den Informationsgehalt einer Nachricht zu messen, ist durch die Kolmogorow-Komplexität gegeben, worin der kürzestmögliche Algorithmus zur Darstellung einer gegebenen Zeichenkette die Komplexität der Nachricht angibt. Ähnlich ist die Logische Tiefe definiert, die sich aber auf die Laufzeit bzw. Zeitkomplexität eines Algorithmus zur Erzeugung der Daten bezieht.
Literatur
- Johanneson, Rolf: Informationstheorie, Addison-Wesley 1992, ISBN 3893194657
- Claude Shannon und Warren Weaver: The Mathematical Theory of Communication, University of Illinois Press 1963, ISBN 0252725484 (Softcover) und ISBN 0252725468 (Hardcover)
- Norbert Bischof: Struktur und Bedeutung, 1998, ISBN 3456830807 (Das Buch ist für Sozialwissenschaftler geschrieben und erklärt mathematische Zusammenhänge Nicht-Mathematikern in sehr verständlicher Weise. Das Kapitel 2 widmet sich der Informationstheorie.)
Weitere Begriffe
- Kolmogorov-Entropie, Kolmogorov-Sinai-Entropie, Maximum-Entropie-Methode, Metrische Entropie, Nat, Ornstein Theorem, Redundanz, Topologische Entropie, Markow-Kette, Renyi-Entropie, Tsallis-Entropie, Theil-Entropie, Negentropie, Entropiekodierung
Weblinks
- http://www.madeasy.de/2/zufallgz.htm
- Einführung der Entropie als Gesamtzufallsmenge mit vielen Beispielen und hilfreichen Erklärungen zur Formel von Shannon.
- http://www.techfak.uni-kiel.de/matwis/amat/mw1_ge/kap_5/advanced/t5_3_2.html
- Entropie und Information, gut erklärt