In der Informationstheorie ist die bedingte Entropie ein Mass fur die Ungewissheit uber den Wert einer Zufallsvariablen X displaystyle X welche verbleibt nachdem das Ergebnis einer anderen Zufallsvariable Y displaystyle Y bekannt wird Die bedingte Entropie wird H X Y displaystyle H X Y geschrieben und hat einen Wert zwischen 0 und H X displaystyle H X der ursprunglichen Entropie von X displaystyle X Sie wird in der gleichen Masseinheit wie die Entropie gemessen Speziell hat sie den Wert 0 wenn aus Y displaystyle Y der Wert von X displaystyle X funktional bestimmt werden kann und den Wert H X displaystyle H X wenn X displaystyle X und Y displaystyle Y stochastisch unabhangig sind Inhaltsverzeichnis 1 Definition 2 Eigenschaften 3 Blockentropie 4 Beispiel 4 1 Keine berucksichtigten Zeichen 4 2 Ein berucksichtigtes Zeichen 4 3 Zwei berucksichtigte Zeichen 4 4 Drei berucksichtigte Zeichen 4 5 Entropie und Informationsgehalt 5 Literatur 6 WeblinksDefinition BearbeitenSeien X displaystyle X nbsp eine diskrete Zufallsvariable und M displaystyle M nbsp ihr Wertevorrat das heisst M displaystyle M nbsp ist eine hochstens abzahlbare Menge mit P X M 1 displaystyle P X in M 1 nbsp Dann ist die Entropie von X displaystyle X nbsp durch H X x M P X x log b P X x displaystyle H X sum x in M P X x log b P X x nbsp definiert wobei fur b displaystyle b nbsp typischerweise die Werte 2 Bit oder e Nat fur die entsprechenden Einheiten angenommen werden Ist fur ein x M displaystyle x in M nbsp die Wahrscheinlichkeit P X x displaystyle P X x nbsp gleich 0 displaystyle 0 nbsp so wird per Konvention P X x log b P X x 0 displaystyle P X x log b P X x 0 nbsp gesetzt der entsprechende Term geht also nicht in die Summe ein Es sei nun A displaystyle A nbsp ein Ereignis mit P A gt 0 displaystyle P A gt 0 nbsp Dann definiert man die bedingte Entropie von X displaystyle X nbsp gegeben A displaystyle A nbsp durch Ersetzen der Wahrscheinlichkeit durch die bedingte Wahrscheinlichkeit d h H X A x M P X x A log b P X x A displaystyle H X A sum x in M P X x A log b P X x A nbsp Jetzt sei Y displaystyle Y nbsp eine diskrete Zufallsvariable mit Wertevorrat L displaystyle L nbsp Dann ist die bedingte Entropie von X displaystyle X nbsp gegeben Y displaystyle Y nbsp definiert als gewichtetes Mittel der bedingten Entropien von X displaystyle X nbsp gegeben den Ereignissen Y y displaystyle Y y nbsp fur y L displaystyle y in L nbsp d h H X Y y L P Y y gt 0 P Y y H X Y y displaystyle H X Y sum y in L P Y y gt 0 P Y y H X Y y nbsp Auf hoherer Abstraktionsebene handelt es sich bei H X A displaystyle H X A nbsp um den bedingten Erwartungswert der Informationsfunktion I X A x log b P X x A displaystyle I X A x log b P X x A nbsp gegeben A displaystyle A nbsp und bei H X Y displaystyle H X Y nbsp um den Erwartungswert der Funktion I X Y x y log b P X x Y y displaystyle I X Y x y log b P X x Y y nbsp Eigenschaften Bearbeiten nbsp Ein gedachtnisloser Kanal verbindet zwei Quellen Die Transinformation I x y ist diejenige Information die von X gesendet und auch von Y empfangen wurde Eine einfache Rechnung zeigt H X Y H X Y H Y displaystyle H X Y H X Y H Y nbsp also ist die Unsicherheit von X displaystyle X nbsp gegeben Y displaystyle Y nbsp gleich der Unsicherheit von X displaystyle X nbsp und Y displaystyle Y nbsp abzuglich der Unsicherheit von Y displaystyle Y nbsp Es ist H X Y H X displaystyle H X Y leq H X nbsp mit Gleichheit genau dann wenn X displaystyle X nbsp und Y displaystyle Y nbsp stochastisch unabhangig sind Dies folgt aus der Tatsache dass H X Y H X H Y displaystyle H X Y H X H Y nbsp genau dann gilt wenn X displaystyle X nbsp und Y displaystyle Y nbsp stochastisch unabhangig sind Ausserdem bedeutet es dass H Y H Y X displaystyle H Y H Y X nbsp ist also die komplette empfangene Information nur Fehlinformation ist Analog geht die komplette Information von der Quelle X verloren so dass dann auch keine Transinformation vorhanden ist Ausserdem gilt H X Y 0 displaystyle H X Y geq 0 nbsp mit Gleichheit genau dann wenn X displaystyle X nbsp funktional von Y displaystyle Y nbsp abhangt d h X f Y displaystyle X f Y nbsp fur eine Funktion f displaystyle f nbsp Blockentropie BearbeitenUbertragen auf eine multivariate Zufallsvariable X displaystyle X nbsp der Lange k displaystyle k nbsp als Darstellung fur einen k displaystyle k nbsp Block von Symbolen x 1 x k displaystyle x 1 dots x k nbsp lasst sich die bedingte Entropie h k displaystyle h k nbsp definieren als die Unsicherheit eines Symbols x k 1 displaystyle x k 1 nbsp nach einem bestimmten vorgegebenen k displaystyle k nbsp Block h k H k 1 H k displaystyle h k H k 1 H k nbsp mit h 0 H 1 displaystyle h 0 H 1 nbsp wobei H i displaystyle H i nbsp die Blockentropie bezeichnet Fur die bedingte Entropie h 1 displaystyle h 1 nbsp also die Unsicherheit eines Symbols nach einem 1 displaystyle 1 nbsp Block folgt h 1 H 2 H 1 H X H Y X H X H Y X displaystyle h 1 H 2 H 1 H X H Y X H X H Y X nbsp Die Definitionen der Blockentropie und der bedingten Entropie sind im Grenzubergang gleichwertig vgl Quellentropie In engem Zusammenhang zur bedingten Entropie steht auch die Transinformation die die Starke des statistischen Zusammenhangs zweier Zufallsgrossen angibt Beispiel BearbeitenSei X eine Quelle die periodisch die Zeichen 00100010001000100010 sendet Nun soll unter Berucksichtigung vorangegangener Zeichen die bedingte Entropie des aktuell zu beobachtenden Zeichens berechnet werden Keine berucksichtigten Zeichen Bearbeiten p 0 P X 0 3 4 displaystyle p 0 P X 0 textstyle frac 3 4 nbsp p 1 P X 1 1 4 displaystyle p 1 P X 1 textstyle frac 1 4 nbsp H X H p 0 p 1 3 4 log 2 3 4 1 4 log 2 1 4 0 811 b i t displaystyle H X H p 0 p 1 textstyle frac 3 4 cdot log 2 textstyle frac 3 4 textstyle frac 1 4 cdot log 2 textstyle frac 1 4 0 811 bit nbsp Die Berechnung erfolgt nach der Definition der Entropie Wahrscheinlichkeitstabelle x 0 x 1P X x 3 4 displaystyle textstyle frac 3 4 nbsp 1 4 displaystyle textstyle frac 1 4 nbsp Ein berucksichtigtes Zeichen Bearbeiten Sei nun X xt und Y xt 1 Es ergeben sich folgende Wahrscheinlichkeiten P X 0 Y 0 2 3 P X 1 Y 0 1 3 displaystyle P X 0 Y 0 textstyle frac 2 3 qquad P X 1 Y 0 textstyle frac 1 3 nbsp P X 0 Y 1 1 P X 1 Y 1 0 displaystyle P X 0 Y 1 1 qquad P X 1 Y 1 0 nbsp H X Y y Y x X P Y y H X x Y y displaystyle H X Y sum y in Y sum x in X P Y y cdot H X x Y y nbsp y Y P Y y H X Y y displaystyle qquad sum y in Y P Y y cdot H X Y y nbsp P Y 0 H X Y 0 P Y 1 H X Y 1 displaystyle qquad P Y 0 cdot H X Y 0 P Y 1 cdot H X Y 1 nbsp 3 4 H X Y 0 H P X 0 Y 0 P X 1 Y 0 1 4 H X Y 1 H P X 0 Y 1 P X 1 Y 1 displaystyle qquad textstyle frac 3 4 cdot begin matrix underbrace H X Y 0 rm H P X 0 Y 0 P X 1 Y 0 4 5ex end matrix textstyle frac 1 4 cdot begin matrix underbrace H X Y 1 rm H P X 0 Y 1 P X 1 Y 1 4 5ex end matrix nbsp 3 4 H 2 3 1 3 1 4 H 1 0 0 0 689 b i t displaystyle qquad textstyle frac 3 4 cdot H textstyle frac 2 3 textstyle frac 1 3 begin matrix textstyle frac 1 4 cdot underbrace H 1 0 rm 0 4 5ex end matrix 0 689 bit nbsp Wahrscheinlichkeitstabellen P X Y x 0 x 1y 0 2 3 displaystyle textstyle frac 2 3 nbsp 1 3 displaystyle textstyle frac 1 3 nbsp y 1 1 displaystyle textstyle 1 nbsp 0 displaystyle textstyle 0 nbsp Wobei gilt P X Y P X x Y y displaystyle P X Y P X x Y y nbsp P x t x x t 1 y displaystyle P x t x x t 1 y nbsp y 0 y 1P Y y displaystyle P Y y nbsp 3 4 displaystyle textstyle frac 3 4 nbsp 1 4 displaystyle textstyle frac 1 4 nbsp Zwei berucksichtigte Zeichen Bearbeiten Sei X xt und Y xt 2 xt 1 Es ergeben sich folgende Wahrscheinlichkeiten P X 0 Y 0 0 1 2 P X 1 Y 0 0 1 2 displaystyle P X 0 Y 0 0 textstyle frac 1 2 qquad P X 1 Y 0 0 textstyle frac 1 2 nbsp P X 0 Y 0 1 1 P X 1 Y 0 1 0 displaystyle P X 0 Y 0 1 1 qquad P X 1 Y 0 1 0 nbsp P X 0 Y 1 0 1 P X 1 Y 1 0 0 displaystyle P X 0 Y 1 0 1 qquad P X 1 Y 1 0 0 nbsp Y 1 1 kommt in der Quelle nie vor braucht also nicht betrachtet zu werden H X Y y Y P Y y H X Y y displaystyle H X Y sum y in Y P Y y cdot H X Y y nbsp 1 2 H X Y 0 0 1 4 H X Y 0 1 1 4 H X Y 1 0 displaystyle textstyle frac 1 2 cdot H X Y 0 0 textstyle frac 1 4 cdot H X Y 0 1 textstyle frac 1 4 cdot H X Y 1 0 nbsp 1 2 H 1 2 1 2 1 4 H 1 0 0 1 4 H 0 1 0 displaystyle textstyle frac 1 2 cdot H textstyle frac 1 2 textstyle frac 1 2 begin matrix underbrace textstyle frac 1 4 cdot H 1 0 rm 0 4 5ex end matrix begin matrix underbrace textstyle frac 1 4 cdot H 0 1 rm 0 4 5ex end matrix nbsp 1 2 b i t displaystyle textstyle frac 1 2 bit nbsp Wahrscheinlichkeitstabellen P X Y X 0 X 1y 0 0 1 2 displaystyle textstyle frac 1 2 nbsp 1 2 displaystyle textstyle frac 1 2 nbsp y 0 1 1 displaystyle textstyle 1 nbsp 0 displaystyle textstyle 0 nbsp y 1 0 1 displaystyle textstyle 1 nbsp 0 displaystyle textstyle 0 nbsp y 1 1 displaystyle textstyle nbsp displaystyle textstyle nbsp Wobei gilt P X Y displaystyle P X Y nbsp P x t x t 2 x t 1 displaystyle P x t mid x t 2 x t 1 nbsp y 0 0 y 0 1 y 1 0 y 1 1 P Y y 1 2 displaystyle textstyle frac 1 2 nbsp 1 4 displaystyle textstyle frac 1 4 nbsp 1 4 displaystyle textstyle frac 1 4 nbsp 0 displaystyle textstyle 0 nbsp Wobei gilt P Y P y t y t 1 displaystyle P Y P y t y t 1 nbsp Drei berucksichtigte Zeichen Bearbeiten H X Y 0 displaystyle H X Y 0 nbsp Sind bereits drei nacheinander folgende Zeichen bekannt so ist damit auch das folgende Zeichen determiniert denn die Quelle verhalt sich ja periodisch Somit erhalt man keine neue Information uber das nachste Zeichen Demnach muss die Entropie null sein Dies kann man auch an der Wahrscheinlichkeitstabelle ablesen P X Y X 0 X 1y 0 0 0 0 displaystyle textstyle 0 nbsp 1 displaystyle textstyle 1 nbsp y 0 0 1 1 displaystyle textstyle 1 nbsp 0 displaystyle textstyle 0 nbsp y 0 1 0 1 displaystyle textstyle 1 nbsp 0 displaystyle textstyle 0 nbsp y 0 1 1 displaystyle textstyle nbsp displaystyle textstyle nbsp y 1 0 0 1 displaystyle textstyle 1 nbsp 0 displaystyle textstyle 0 nbsp y 1 0 1 displaystyle textstyle nbsp displaystyle textstyle nbsp y 1 1 0 displaystyle textstyle nbsp displaystyle textstyle nbsp y 1 1 1 displaystyle textstyle nbsp displaystyle textstyle nbsp Wobei gilt P X Y P X x Y y displaystyle P X Y P X x Y y nbsp P X x t Y x t 3 x t 2 x t 1 displaystyle P X x t Y x t 3 x t 2 x t 1 nbsp Unmogliche Ereignisse werden hier mit gekennzeichnet z B bei y 1 0 1 Diese Ausgabe wird die gegebene Quelle nie liefern da nach einer Eins immer drei Nullen folgen Man sieht dass in der Tabelle keine anderen Wahrscheinlichkeiten auftreten als 0 oder 1 Da nach der Definition der Entropie gilt H 0 1 H 1 0 0 displaystyle H 0 1 H 1 0 0 nbsp muss schliesslich die Entropie H X Y 0 displaystyle H X Y 0 nbsp sein Erlauterung zu den WahrscheinlichkeitstabellenDie Tabellen beziehen sich auf die obige Beispielzeichensequenz P X Y x 0 x 1y 0 2 3 displaystyle textstyle frac 2 3 nbsp 1 3 displaystyle textstyle frac 1 3 nbsp y 1 1 displaystyle textstyle 1 nbsp 0 displaystyle textstyle 0 nbsp Wobei gilt P X Y P X x Y y P X x t Y x t 1 p x t x t 1 displaystyle P X Y P X x Y y P X x t Y x t 1 p x t x t 1 nbsp Hier betrachtet man ein Zeichen X displaystyle X nbsp unter der Bedingung des vorangegangenen Zeichens Y displaystyle Y nbsp Ist beispielsweise ein Zeichen Y 1 displaystyle Y 1 nbsp so lautet die Frage Mit welcher Wahrscheinlichkeit ist das darauffolgende Zeichen X 0 displaystyle X 0 nbsp bzw X 1 displaystyle X 1 nbsp Fur Y 1 displaystyle Y 1 nbsp ist das nachste Zeichen X displaystyle X nbsp immer 0 displaystyle 0 nbsp Somit ist P X 0 Y 1 1 displaystyle P X 0 Y 1 1 nbsp Ausserdem folgt daraus dass P X 1 Y 1 0 displaystyle P X 1 Y 1 0 nbsp ist da die Zeilensumme immer Eins ist P X xt 0 xt 1xt 1 0 1 2 displaystyle textstyle frac 1 2 nbsp 1 4 displaystyle textstyle frac 1 4 nbsp xt 1 1 1 4 displaystyle textstyle frac 1 4 nbsp 0 displaystyle textstyle 0 nbsp Wobei gilt P X P X x t x t 1 P p x t p x t 1 p x t x t 1 displaystyle P X P X x t x t 1 P p x t p x t 1 p x t x t 1 nbsp Hier betrachtet man die Auftrittshaufigkeit einer Zeichenkombination Man kann aus der Tabelle lesen dass die Buchstabenkombinationen 0 1 und 1 0 genauso haufig auftreten Die Summe aller Matrixeintrage ergibt Eins Entropie und Informationsgehalt Bearbeiten Die Entropie fallt bei diesem Beispiel umso starker je mehr Zeichen berucksichtigt werden siehe auch Markow Prozess Wenn die Anzahl der berucksichtigten Zeichen hinreichend gross gewahlt wird so konvergiert die Entropie gegen Null Mochte man den Informationsgehalt der gegebenen Zeichenfolge aus n 12 Zeichen berechnen so erhalt man nach Definition Iges n H X Y bei keinem berucksichtigten Zeichen 9 39 bit Gesamtinformation Informationsgehalt statistisch unabhangiger Ereignisse einem berucksichtigten Zeichen 8 26 bit Gesamtinformation zwei berucksichtigten Zeichen 6 bit Gesamtinformation drei berucksichtigten Zeichen 0 bit Gesamtinformation Literatur BearbeitenMartin Werner Information und Codierung Grundlagen und Anwendungen 2 Auflage Vieweg Teubner Verlag Wiesbaden 2008 ISBN 978 3 8348 0232 3 Karl Steinbuch Werner Rupprecht Nachrichtentechnik Eine einfuhrende Darstellung Springer Verlag Berlin Heidelberg 1967 R Mathar Informationstheorie Diskrete Modelle und Verfahren B G Teubner Verlag Stuttgart 1996 ISBN 978 3 519 02574 0 Weblinks BearbeitenVorlesungsskript Gemeinsame Entropie und bedingte Entropie abgerufen am 19 Januar 2018 Bedingte Entropie abgerufen am 19 Januar 2018 Statistische Methoden in der Sprachverarbeitung abgerufen am 19 Januar 2018 Datensicherheit und Shannons Theorie abgerufen am 19 Januar 2018 Wahrscheinlichkeit Statistik Induktion abgerufen am 19 Januar 2018 Abgerufen von https de wikipedia org w index php title Bedingte Entropie amp oldid 199094765
