Upload
others
View
0
Download
0
Embed Size (px)
Citation preview
Kapitel 3: Entropie
Entropie I InformationstheorieCopyright M. Gross, ETH Zürich 2006, 2007
2
Motivation
Wir erinnern uns: Um eine Zufallsvariable mit Nverschiedenen, gleichwahrscheinlichen Zuständen binär zu codieren, benötigen wir
Die Information steht in direktem Zusammenhang mit der Unsicherheit (Entropie) über den Ausgang eines ZufallsexperimentesWie kann diese Unsicherheit quantitativ erfasst werden?Statt einer direkten Definition stellen wir eine Reihe von Anforderungen auf
⎡ ⎤Bitslog2 N ⎡ ⎤Bitsplog2 N−
Entropie I InformationstheorieCopyright M. Gross, ETH Zürich 2006, 2007
3
Anforderungen I
Die Unsicherheit über ein Experiment soll unabhängig von der Nomenklatur sein und nur von den Wahrscheinlichkeiten der Elementarereignisse abhängen
Beispiel: Beim fairen Münzwurf soll die Unsicherheit gleich gross sein, egal ob wir die Ereignisse „Kopf“ und „Zahl“ oder „0“ und „1“ nennen
Entropie I InformationstheorieCopyright M. Gross, ETH Zürich 2006, 2007
4
Anforderungen II
Die Unsicherheit über ein Experiment soll unabhängig von der Nomenklatur sein und nur von den Wahrscheinlichkeiten der Elementarereignisse abhängen
Die Unsicherheit ist eine Funktion H, welche jeder Wahrscheinlichkeitsverteilung eine reelle Zahl zu-ordnet, im Falle endlicher Zufallsexperimente also jeder Liste [p1,..,pL] sich zu 1 summierender ZahlenOhne Beschränkung der Allgemeinheit können wir daher eine solche Liste mit L ≥ 1 Elementen als geordnet auffassen, also
Lppp ≥≥≥ ...21
Entropie I InformationstheorieCopyright M. Gross, ETH Zürich 2006, 2007
5
Anforderungen III
Ereignisse mit der Wahrscheinlichkeit 0 sollen keinen Einfluss haben:
Allgemein soll gelten, dass für Experimente mit gleichwahrscheinlichen Ereignissen die Entropie mit der Anzahl der möglichen Ereignisse zunimmt:
[ ] [ ])0,,...,(),...,( 11 LL ppHppH =
⎟⎟⎠
⎞⎜⎜⎝
⎛⎥⎦⎤
⎢⎣⎡
++
Entropie I InformationstheorieCopyright M. Gross, ETH Zürich 2006, 2007
6
Anforderungen IV
Die Entropie eines Münzwurfes soll umso kleiner sein, je unfairer oder asymmetrischer die Münze ist, und ist maximal für einen fairen Münzwurf
H([p1, ..,pL]) ist maximal, wenn p1=…=pL=1/L
[ ] [ ])1,()1,(2/1 qqHppHqp −
Entropie I InformationstheorieCopyright M. Gross, ETH Zürich 2006, 2007
7
Anforderungen V
Die Entropie eines Experimentes, welches aus zwei unabhängigen Einzelexperimenten besteht, soll gleich der Summe der Einzelentropien sein
Wenn L=M=1, dann gilt H(1)=0
⎟⎟⎠
⎞⎜⎜⎝
⎛⎥⎦⎤
⎢⎣⎡+⎟⎟
⎠
⎞⎜⎜⎝
⎛⎥⎦⎤
⎢⎣⎡=⎟⎟
⎠
⎞⎜⎜⎝
⎛⎥⎦⎤
⎢⎣⎡
MMH
LLH
LMLMH 1,...,11,...,11,...,1
Die Entropie eines Experimentes mit nur einem einzigenmöglichen Ausgang ist also 0. Sie enthält keineInformation
Entropie I InformationstheorieCopyright M. Gross, ETH Zürich 2006, 2007
8
Anforderungen VI
Normierung: Es ist sinnvoll, die Entropie eines fairen Münzwurfs auf 1 zu normieren, da man ein Bit benötigt, um das Resultat darzustellen
Glattheit: Kleine Änderungen in der Wahrscheinlichkeitsverteilung sollen nur kleine Änderungen in der Entropie bewirken
121,
21
=⎟⎟⎠
⎞⎜⎜⎝
⎛⎥⎦⎤
⎢⎣⎡H
Entropie I InformationstheorieCopyright M. Gross, ETH Zürich 2006, 2007
9
Definitionen
Man kann zeigen, dass die einzige Funktion, welche alle diese Forderungen erfüllt, wie folgt definiert sein mussDefinition 1: Die Entropie einer diskreten Wahrscheinlichkeitsverteilung [p1, ...,pL] ist:
Beispiel: Die Entropie der dreiwertigen Verteilung[0.7, 0.27655, 0.02345] ist 1 bit, wie beim fairen MünzwurfBesonders einfach ist die Entropieberechnung, wenn alle Wahrscheinlichkeiten negative Zweierpotenzen sind!
[ ]( ) iL
iiL ppppH 2
11 log,..., ∑
=
−=
Entropie I InformationstheorieCopyright M. Gross, ETH Zürich 2006, 2007
10
Definitionen
Die Zufallsvariable X nehme die Zustände {x1,…,xL} mit den Wahrscheinlichkeiten pX(xi) anDefinition 2: Die Entropie einer diskreten Zufallsvariablen X ist:
Anmerkung: Auch für L=∞ kann die obige Summe einen endlichen Wert annehmen
Die Menge {x1,…,xL} aller Zustände von X nennen wir auch das Alphabet von X
)(log)()( 21
iX
L
iiX xpxpXH ∑
=
−=
Entropie I InformationstheorieCopyright M. Gross, ETH Zürich 2006, 2007
11
Informationsquelle 1
Gegeben: Informationsquelle mit Alphabet {a,b,c,d}
Ziel: möglichst optimale Codierung (Huffman)
81d
81c
41)b(
21)a( ==== )p()p(pp
111(d)110(c)10)(b
0)a(
====
CCCC
)b(C
)a(C
)d(C)c(C
0 1
1
1
0
0
Entropie I InformationstheorieCopyright M. Gross, ETH Zürich 2006, 2007
12
Informationsquelle 1
Entropie:
Mittlere Codelänge:
1 1 1( ) 1 2 3 2 1.75 Bits2 4 8
H X = ⋅ + ⋅ + ⋅ ⋅ =
Bits 75.123812
411
21
))(())((
)]([)L(
=⋅⋅+⋅+⋅=
⋅=
=
∑=
iCpiCl
ClECd
ai)b(C
)a(C
)d(C)c(C
0 1
1
1
0
0
Entropie I InformationstheorieCopyright M. Gross, ETH Zürich 2006, 2007
13
Informationsquelle 2
Alphabet {a,b,c}
31c
31)b(
31)a( === )p(pp
11(c) ,10)(b ,0)a( === CCC3
2 21
1( ) log 3 log 3 1.58 Bits3i
H X=
= = =∑
Bits 66.122311
31
))(())(()(
=⋅⋅+⋅=
⋅= ∑=
iCpiClCLc
ai
)b(C
)a(C
)c(C
0 1
10
Entropie I InformationstheorieCopyright M. Gross, ETH Zürich 2006, 2007
14
Anmerkungen
Beides sind präfixfreie Codes
acdaab = 01101110010
ist eindeutig dekodierbar
Minimale Anzahl Fragen zur Bestimmung von XIst X=a?Ist X=b?
Erwartungswert
[ ] 1)()( min +
Entropie I InformationstheorieCopyright M. Gross, ETH Zürich 2006, 2007
15
Binäre Entropiefunktion
Die Wahrscheinlichkeitsverteilung einer binären Zufallsvariablen X ist durch pX(0)=p vollständig beschrieben, da gilt: pX(1)=1-p Die Entropie kann also als Funktion von paufgefasst werden
Sie ist für 0
Entropie I InformationstheorieCopyright M. Gross, ETH Zürich 2006, 2007
16
Binäre Entropiefunktion
Entropie I InformationstheorieCopyright M. Gross, ETH Zürich 2006, 2007
17
Entropie als Erwartungswert
Anmerkung: Wir verwenden die Konvention
Dennoch gilt, dass Werte mit der Wahrscheinlichkeit 0 von der Betrachtung ausgeschlossen werdenDann kann die Entropie auch als Erwartungswert einer reellwertigen Funktion aufgefasst werden:
[ ])(log)( 2 XPEXH X−=
0)0(log0 2 =⋅
Entropie I InformationstheorieCopyright M. Gross, ETH Zürich 2006, 2007
18
Schranken für die Entropie
Theorem: Es sei χ = {x1,…,xL} die Menge der möglichen Zustände der Zufallsvariablen X.Dann gilt:
oder auch
Gleichheit gilt auf der linken Seite, wenn pX(x)=1 für genau ein xGleichheit gilt auf der rechten Seite, wenn p1=,…,=pL=1/L
χ2log)(0 ≤≤ XH
[ ] LppH L 21 log),...,(0 ≤≤
Entropie I InformationstheorieCopyright M. Gross, ETH Zürich 2006, 2007
19
Beweis I
Beweis: Der linke Teil der Ungleichung folgt direkt aus der Tatsache, dass die Funktion
für 0 < x < 1 streng positiv ist und nur für x = 1 gemäss Konvention gleich 0 ist
Die rechte Ungleichung folgt aus der Jensen-Ungleichung und der Tatsache, dass die Funktion
konkav ist
xxxf 2log)( −=
xxf 2log)( =
Entropie I InformationstheorieCopyright M. Gross, ETH Zürich 2006, 2007
20
Beweis II
Es gilt:
Der letzte Schritt folgt aus
Konvention: Im Folgenden wird die Basis 2 für den Logarithmus angenommen und nicht mehr explizit geschrieben
χ222 log)(1log
)(1log)( =⎟⎟
⎠
⎞⎜⎜⎝
⎛⎥⎦
⎤⎢⎣
⎡≤⎥
⎦
⎤⎢⎣
⎡=
XPE
XPExH
XX
χ==⎥⎦
⎤⎢⎣
⎡∑= )(
1)()(
11 XP
XPXP
EX
L
iX
X
Entropie I InformationstheorieCopyright M. Gross, ETH Zürich 2006, 2007
21
Konvexität
Definition: Eine Funktion f(x) heisst konvex auf einem Intervall [a,b], wenn für alle
Eine Funktion ist strikt konvex, wenn Gleichheit nur für λ=0 und λ=1 giltEine Funktion f ist konkav, wenn –f konvex istDer Graph einer differenzierbaren, konvexen Funktion liegt immer oberhalb jeder Tangente
:gilt]1,0[und],,[, 2121 ∈≠∈ λxxbaxx
)()1()())1(( 2121 xfxfxxf λλλλ −+≤−+
Entropie I InformationstheorieCopyright M. Gross, ETH Zürich 2006, 2007
22
Konvexität
Existiert f′′(x) einer Funktion f auf einem offenen oder geschlossenen Intervall [a,b] und gilt f′′(x)>0, dann ist f konvex
Entropie I InformationstheorieCopyright M. Gross, ETH Zürich 2006, 2007
23
Beweis Konvexität
Taylorreihe von f um x0
x=x1
x=x2
[ ] 0)("gilt für 0* ≥∈ *xf...xxx
2* 0
0 0 0( )( ) ( ) '( ) ( ) ''( )
2x xf x f x f x x x f x −= + ⋅ − + ⋅
λλ ⋅−⋅−⋅+≥→ |)()1()(')()( 21001 xxxfxfxf
210 )1( sei xxx λλ −+=
)1(|)()(')()( 12002 λλ −⋅−⋅⋅+≥→ xxxfxfxf
)()1()())1(( 2121 xfxfxxf ⋅−+⋅≤⋅−+⋅→ λλλλ
Entropie I InformationstheorieCopyright M. Gross, ETH Zürich 2006, 2007
24
Jensen-Ungleichung
Theorem: Für eine konvexe Funktion f und eine Zufallsvariable X gilt:
Entsprechend gilt für eine konkave Funktion gund eine Zufallsvariable X
[ ] [ ])()( XEfXfE ≥
[ ] [ ])()( XEgXgE ≤
Entropie I InformationstheorieCopyright M. Gross, ETH Zürich 2006, 2007
25
Beweis Jensen-Ungleichung
Wir gehen davon aus, dass f mindestens einmal differenzierbar istSei ax+b die Tangente an f im Punkt x=E[X]Wir ersetzen die Funktion in x durch Ihre TangenteDann gilt aufgrund der Linearität von E
Dies gilt aufgrund der Tatsache, dass der Graph der konvexen Funktion immer oberhalb der Tangente liegt
[ ] [ ] [ ] [ ])()( XfEbaXEbXaEXEf ≤+=+=
Entropie I InformationstheorieCopyright M. Gross, ETH Zürich 2006, 2007
26
Verbund-Entropie
Es sei (X,Y) ein Paar von Zufallsvariablen Die gemeinsame Entropie (Verbundentropie) zweier Zufallsvariablen X und Y ist gegeben durch
Theorem: Es gilt:
Gleichheit gilt genau dann, wenn Y durch Kenntnis von X eindeutig bestimmt ist, Y also keine neue Information enthält, also für ein y gilt
[ ]),(log),(log),()(),(
YXpEyxpyxpXYH XYyx
XYXY −=−= ∑
)()( XYHXH ≤
1),( =yxpYX
Entropie I InformationstheorieCopyright M. Gross, ETH Zürich 2006, 2007
27
Beweis Verbund-Entropie
H(X) und H(XY) sind Erwartungswerte:
Im Rahmen der Verbundwahrscheinlichkeiten zweier Zufallsvariablen haben wir folgende Gesetzmässigkeit kennengelernt:
Dies gilt für alle möglichen Zustandspaare (x,y)
[ ]),(log)( YXpEXYH XY−=
)(),( xpyxp XXY ≤
Entropie I InformationstheorieCopyright M. Gross, ETH Zürich 2006, 2007
28
Verbund-Entropie
Folgendes Theorem ist von zentraler Bedeutung:Theorem: Es gilt
Gleichheit gilt genau dann, wenn Y und X statistisch unabhängig sindDer Beweis erfolgt durch Einsetzen sowie Anwendung der Jensen-Ungleichung:
)()()( YHXHXYH +≤
[ ]),(log)(log)(log)()()(
YXpYpXpEXYHYHXH
XYYX +−−=−+
Die Entropie des Verbundereignisses XY ist höchstens so gross, wie die Summe der Entropien der Einzelereignisse.
Entropie I InformationstheorieCopyright M. Gross, ETH Zürich 2006, 2007
29
Bild dazu
H(Y)H(X)
H(XY)H(XY)=H(X) + H(Y)
H(XY)=H(X)