Information und Kommunikation

Hartmut KlauckUniversität Frankfurt

SS 0716.4.

Organisatorisches

• Vorlesungen:– Montag 14-16 ct SR 11– Freitag 14-16 ct SR 11

• Übung:– Donnerstag 10-12 ct, Raum 307 (Dirk Brendel)

• Schein:– Gebiet T2, ThBI– Durch Fachgespräch

• Voraussetzung: Vordiplom• Vorkenntnisse:

– Wahrscheinlichkeitstheorie– Lineare Algebra

Übungszettel

• Es wird regelmäßig Übungszettel geben, aber keine Übungspunkte

• Trotzdem dringend zur Bearbeitung empfohlen

Literatur

• Webseite zur Vorlesung:– http://www.thi.informatik.uni-frankfurt.de/~kla

uck/IK07.html

• Cover, Thomas: Elements of Information Theory (Wiley)

• Kushilevitz, Nisan: Communication Complexity (Cambrige UP)

Einleitung

• Themen der Vorlesung:– Informationstheorie– Kommunikationskomplexität– Anwendungen auf andere Modelle

Information

• Wikipedia:– Formaler ist Information die Beseitigung

von Unbestimmtheit bzw. die Beseitigung einer Ungewissheit durch Auskunft, Aufklärung, Mitteilung, Benachrichtigung oder Kenntnis über Gegenstände und Phänomene.

Information

• Wikipedia: [Informationstheorie]Unter quantitativen Gesichtspunkten der Wahrscheinlichkeit bezieht sich dagegen Information als Terminus in der Informationstheorie auf mathematisch beschreibbare Eigenschaften im Prozess zwischen Sender und Empfänger. Die Informationstheorie beschäftigt sich dabei mit Zeichen als Signale, mit Kodes und Kommunikation. Auch in der Informationstheorie ist der Neuigkeitswert von Bedeutung.

Informationstheorie

• Die Informationstheorie beschäftigt sich mit– Maßen von Information– Übertragung von Information über

Kanäle• Dies erzeugt im allgemeinen Fehler

– Rekonstruktion der Information• Fehlerkorrigierende Codes• Datenkompression

Informationstheorie

• Im allgemeinen wird in der Informationstheorie das folgende Kanalmodell verwendet:

• Die betrachtete Kommunikation ist also– Ein Monolog– Dient dazu, die Eingabe der Quelle ans Ziel zu

transportieren

Kommunikation

• Im zweiten Teil der Vorlesung betrachten wir ein komplizierteres Modell

• Wir erlauben Kommunikation mit beliebiger Interaktion

• Wir betrachten die Berechnung von Funktionen der Eingabe

Kommunikationskomplexität• Das Kommunikationsmodell• Spieler Alice und Bob erhalten Eingaben x bzw. y

• Die Spieler kommunizieren gemäß eines Protokolls und berechnen f(x,y)

• Wir sind interessiert an der notwendigen Kommunikation, um eine Funktion f(x,y) zu berechnen

Ein Problem der Informationstheorie

• Die Quelle (Alice) hat Eingaben x2{0,1}n, mit einer Wahrscheinlichkeitsverteilung p(x)

• Die Eingabe x soll zum Empfänger (Bob) übertragen werden

• Der Kanal sei fehlerfrei• Wieviel muss kommuniziert werden?

Ein Problem der Kommunikationskomplexität

• Alice hat eine Eingabe x2 {0,1}n, Bob eine Eingabe y2 {0,1}n

• Alice und Bob wollen (mit Hilfe von Kommunikation) entscheiden, ob x=y

• Wieviel muss kommuniziert werden?

Varianten dieser Fragen

• Informationstheorie:– Betrachtung verschiedener Kanäle– Beispiel: Jedes übertragene Zeichen geht

mit Wahrscheinlichkeit p verloren (und der Verlust wird bemerkt)

– Beispiel: Jedes übertragene Zeichen wir mit Wahrscheinlichkeit p verfälscht

– Welche Kapazität hat ein Kanal, d.h. wieviel Information kann man nun übertragen?

Varianten dieser Fragen

• Kommunikationskomplexität– Im allgemeinen betrachtet man hier fehlerfreie

„Kanäle“, da die damit zusammenhängenden Probleme durch die Informationstheorie gelöst werden können

– Verschiedene „Modi“ von Kommunikation, z.B. randomisierte Kommunikation, nichtdeterministische Kommunikation

– Wie beweist man untere und obere Schranken im Kommunikationsmodell?

– Anwendungen auf andere Modelle (VLSI, Schaltkreise, Automaten, Datastreams etc.)

Überblick über die Vorlesung

• Wir werden zunächst die grundlegenden Begriffe der Informationstheorie betrachten– Entropie, Information, …

• Datenkompression und fehlerkorrigierende Codes

• Exkurs: Kolmogorov Komplexität• Dann wechseln wir zur

Kommunikationskomplexität• Insbesondere Anwendungen der Begriffe

aus der Informationstheorie• Anwendungen auf untere Schranken

Teil I

Informationstheorie

Historisches

• Die Informationstheorie wurde von Claude Shannon (1916-2001) begründet

• Wichtige Arbeit: A Mathematical Theory of Communication (1948)

Was ist Information?

• Information: „A difference that makes a difference“ (Bateson)

• Unsere grundlegende Informationseinheit ist das bit

• „binary digit“• Genauer gesagt: ein Bit ist der

Informationsgehalt, der in einer Auswahl aus zwei gleichwahrscheinlichen Möglichkeiten enthalten ist

Was ist Information?

• Grundlegend ist dabei eine Wahrscheinlichkeitsverteilung auf den möglichen Ereignissen– Wenn nur ein Ereignis möglich ist,

erhalten wir keine Information durch das Eintreten des Ereignisses

– Wenn n Ereignisse möglich sind, sollte die erhaltene Information der Länge einer effizienten Beschreibung des Ereignisses entsprechen

Was ist Information?

• Die Informationstheorie ist daher eine statistische Theorie der Information

• Individuelle Objekte enthalten somit keine Information, erst im Kontext mit anderen Möglichkeiten im Rahmen einer Wahrscheinlichkeitsverteilung ergibt sich Information

• In der Theorie der Kolmogorov-Komplexität hingegen kann der Informationsgehalt individueller Objekte betrachtet werden.

Entropie

• Usprünglich ein Begriff aus der Physik/Thermodynamik

• Ein Maß der Ungeordnetheit eines physikalischen Zustandes

• Wärme: hohe Entropie• Von Shannon in die

Informationstheorie eingeführt

Entropie

• Seien Ereignisse 1,…,n möglich• p(1),…,p(n) sei eine

Wahrscheinlichkeitsverteilung• Üblicherweise betrachten wir eine

Zufallsvariable X Elementarereignissen 1,…,n• Dann ist die Entropie durch

H(X)=-i=1,…,n p(i) log (p(i))gegeben

• Der Logarithmus ist immer zur Basis 2• Es wird die Konvention 0 log 0 = 0 verwendet

Entropie

• Entropie ist ein Erwartungswert– H(X)=i=1,…,n p(i) log (1/p(i))

– Erwartungswert von log(1/p(i))

• Entropie ist ein Maß für Unsicherheit, Nichtwissen über den Wert von X

Eigenschaften der Entropie

1. H(X)¸ 0 für alle X2. H(X)· log n für alle X, die n Werte

annehmen können3. H(X)=0 für Zufallsvariablen X,

deren Verteilung auf einem Ereignis konzentriert sind

4. H(X)=log n, gdw X uniform verteilt ist

Beweis

• 1) 0· p(i)· 1, daher ist log (1/p(i))¸ 0 und somit H(X)¸ 0

• 3) Wenn p(i)=1 für ein i, dann sind alle anderen p(i)=0, und H(X)=0.Wenn H(X)=0, dann sind alle Summanden entweder -0 log 0 oder-1 log 1, daher ist ein p(i)=1, die anderen p(i)=0.

Beweis

• 2) H(X)· log n für X mit Ereignissen 1,…,n– Beispiel: uniforme Verteilung, alle

p(i)=1/n– H(X)=n ¢ 1/n ¢ log n = log n– Fakt 1.1: [Jensens Ungleichung]

• Sei f eine konvexe Funktion und X eine Zufallsvariable. Dann gilt: E[f(X)]¸ f(E[x])

• Sei f eine konkave Funktion und X eine Zufallsvariable. Dann gilt: E[f(X)]· f(E[x])

Beweis

• 2)

• H(X)=i=1,…,n p(i) log (1/p(i))

· log i=1,…,n p(i) ¢ (1/p(i))

=log i=1,…,n 1 = log n

• log ist konkav

• 4) beweisen wir später

Die binäre Entropie

• Sei X eine Zufallsvariable auf {0,1}• p sei Ws von 0, 1-p Ws von 1• Wir setzen

H(p)=H(X)=-p log p –(1-p)log (1-p)